Cod sursa(job #2611689)

Utilizator SergiuS3003Sergiu Stancu Nicolae SergiuS3003 Data 7 mai 2020 13:57:11
Problema Peste Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f ( "peste.in" );
ofstream g ( "peste.out" );
struct plasa
{
    int p, t;
};
plasa v[50002];
bool cmp ( plasa a, plasa b )
{
    return a.p > b.p;
}
int N, K, T;
long long dp[1001], rasp[50001];
int cate[1001];
int main()
{
    f >> N >> K >> T;
    int tmax = 0;

    for ( int i = 1; i <= N; i++ )
    {
        f >> v[i].p >> v[i].t;
        tmax = max ( tmax, v[i].t );
    }

    sort ( v + 1, v + N + 1, cmp );

    for ( int i = 1; i <= N; i++ )
            for ( int j = v[i].t; j <= tmax; j++ )
            {
                if ( cate[j] >= K )
                    break;

                cate[j]++;
                dp[j] += v[i].p;
            }

    for ( int i = 1; i <= tmax; i++ )
        for ( int j = 0; j <= T - i; j++ )
            rasp[i + j] = max ( rasp[i + j], rasp[j] + dp[i] );

    long long mx = 0;

    for ( int i = 1; i <= T; i++ )
        mx = max ( mx, rasp[i] );

    g << mx;
    return 0;
}