oj.uz

Submission #791033

# Submission time Handle Problem Language Result Execution time Memory
791033 2023-07-23T11:03:54 Z alexander707070 Carnival Tickets (IOI20_tickets) C++14
51 / 100
 3000 ms 144032 KB 
#include<bits/stdc++.h>
#include "tickets.h"
#define MAXN 1507
using namespace std;

const long long inf=1e15;

int n,m,sol[MAXN],k,rest[MAXN],br,maxs,ind[MAXN];
long long pref[MAXN][MAXN],suff[MAXN][MAXN];
pair<int,int> s[MAXN][MAXN];
vector<int> curr;
vector< vector<int> > res;

int li[MAXN][MAXN*20],tim,used[MAXN];
long long dp[MAXN][MAXN*20],ans;

long long ff(int pos,int balance){
    if(balance<0 or balance>20*m)return -inf;
    if(pos==-1 and balance==10*m)return 0;
    else if(pos==-1)return -inf;

    if(li[pos][balance]==tim)return dp[pos][balance];
    li[pos][balance]=tim;
    dp[pos][balance]=-inf;

    for(int i=0;i<=k;i++){
        dp[pos][balance]=max(dp[pos][balance],ff(pos-1,balance-i+k-i)+suff[ind[pos]][k-i]-pref[ind[pos]][i]);
    }

    return dp[pos][balance];
}

void solve(int pos,int balance){
    if(pos==-1)return;

    for(int i=0;i<=k;i++){
        if(ff(pos,balance)==ff(pos-1,balance-i+k-i)+suff[ind[pos]][k-i]-pref[ind[pos]][i]){
            sol[ind[pos]]=i; rest[ind[pos]]=k-i;
            solve(pos-1,balance-i+k-i);
            return;
        }
    }
}

long long find_maximum(int K,vector< vector<int> > x){
    n=int(x.size()); m=int(x[0].size()); k=K;
    res.resize(n);

    for(int i=0;i<n;i++){
        res[i].resize(m); ind[i]=i;
        for(int f=0;f<m;f++){
            s[i][f]={x[i][f],f};
            res[i][f]=-1;
        }
        sort(s[i],s[i]+m);

        for(int f=0;f<m;f++){
            pref[i][f+1]=s[i][f].first;
            pref[i][f+1]+=pref[i][f];
        }
        for(int f=m-1;f>=0;f--){
            suff[i][m-f]=s[i][f].first;
            suff[i][m-f]+=suff[i][m-f-1];
        }   
    }

    random_shuffle(ind,ind+n);

    tim++; solve(n-1,10*m);
    ans=ff(n-1,10*m);

    for(int i=0;i<k;i++){
        br=n/2; tim++;

        for(int f=0;f<n/2;f++){
            maxs=n;
            for(int w=0;w<n;w++){
                if(sol[w]>sol[maxs] and used[w]!=tim)maxs=w;
            }

            res[maxs][s[maxs][sol[maxs]-1].second]=i;
            sol[maxs]--; used[maxs]=tim;
        }

        for(int f=0;f<n;f++){
            if(used[f]!=tim){
                res[f][s[f][m-rest[f]].second]=i;
                rest[f]--;
            }
        }
    }

    allocate_tickets(res);
    return ans;
}


/*
int main(){
    cout<<find_maximum(2, {{0, 2, 5},{1, 1, 3}})<<"\n";
}
*/

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Incorrect 1 ms 2004 KB Contestant returned 18919508441 but the tickets gives a total value of 18862974431
5 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 2 ms 2260 KB Output is correct
5 Correct 22 ms 11724 KB Output is correct
6 Correct 522 ms 144032 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 16 ms 3536 KB Output is correct
5 Correct 744 ms 31052 KB Output is correct
6 Execution timed out 3083 ms 109308 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 29 ms 3552 KB Output is correct
5 Correct 1433 ms 31480 KB Output is correct
6 Correct 529 ms 2712 KB Output is correct
7 Incorrect 40 ms 36044 KB Contestant returned 3777370616692 but the tickets gives a total value of 3777350955124
8 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 2 ms 2260 KB Output is correct
3 Correct 3 ms 2644 KB Output is correct
4 Correct 11 ms 3336 KB Output is correct
5 Correct 16 ms 3560 KB Output is correct
6 Correct 23 ms 3612 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 2132 KB Output is correct
9 Correct 19 ms 3600 KB Output is correct
10 Correct 19 ms 3540 KB Output is correct
11 Correct 26 ms 3592 KB Output is correct
12 Correct 26 ms 3632 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 2 ms 2260 KB Output is correct
3 Correct 3 ms 2644 KB Output is correct
4 Correct 11 ms 3336 KB Output is correct
5 Correct 16 ms 3560 KB Output is correct
6 Correct 23 ms 3612 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 2132 KB Output is correct
9 Correct 19 ms 3600 KB Output is correct
10 Correct 19 ms 3540 KB Output is correct
11 Correct 26 ms 3592 KB Output is correct
12 Correct 26 ms 3632 KB Output is correct
13 Correct 24 ms 12836 KB Output is correct
14 Correct 57 ms 21164 KB Output is correct
15 Correct 732 ms 31036 KB Output is correct
16 Correct 1444 ms 31504 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 8 ms 8148 KB Output is correct
19 Correct 5 ms 7252 KB Output is correct
20 Correct 930 ms 30380 KB Output is correct
21 Correct 943 ms 30144 KB Output is correct
22 Correct 1308 ms 30564 KB Output is correct
23 Correct 1309 ms 30412 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Incorrect 1 ms 2004 KB Contestant returned 18919508441 but the tickets gives a total value of 18862974431
5 Halted 0 ms 0 KB -