# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
300508 | 2020-09-17T08:18:21 Z | daniel920712 | Carnival Tickets (IOI20_tickets) | C++14 | 797 ms | 84004 KB |
#include "tickets.h" #include <vector> #include <algorithm> using namespace std; struct A { int where; int con; }tt[1505]; vector < vector < int > > answer; vector < int > row; vector< vector<int> > all; vector < int > how; bool have[1505][1505]; bool use[1505]={0}; long long DP[1505][1505]; int a[1505]; int b[1505]; int N,M; long long F(int here,int con) { if(con>N/2) return -1e18; if(here==N&&con!=N/2) return -1e18; if(here==N) return 0; if(have[here][con]) return DP[here][con]; have[here][con]=1; DP[here][con]=max(F(here+1,con+1)+all[here][M-1],F(here+1,con)-all[here][0]); return DP[here][con]; } void F2(int here,int con) { if(here==N) return; //printf("%d %d\n",F(here+1,con+1)+all[here][M-1],F(here+1,con)-all[here][0]); if(F(here+1,con+1)+all[here][M-1]>F(here+1,con)-all[here][0]) { //printf("aa\n"); F2(here+1,con+1); answer[here][M-1]=0; } else { F2(here+1,con); answer[here][0]=0; } } long long find_maximum(int k,vector< vector<int> > x) { all=x; N=x.size(); M=x[0].size(); int i,j,l,t,ok,now; long long ans=0; for(i=0;i<M;i++) row.push_back(-1); for(i=0;i<N;i++) { answer.push_back(row); for(j=0;j<M;j++) how.push_back(x[i][j]); } if(k==1) { ans=F(0,0); F2(0,0); } else { sort(how.begin(),how.end()); for(i=0;i<N*M/2;i++) ans-=how[i]; for(i=N*M/2;i<N*M;i++) ans+=how[i]; for(i=0;i<N;i++) { a[i]=0; b[i]=N-1; } for(i=0;i<M;i++) { for(j=0;j<N;j++) use[j]=0; for(j=0;j<N;j++) { if(use[j]) continue; if(x[j][a[j]]<=how[N*M/2-1]) { answer[j][a[j]]=i; for(k=j+1;k<N;k++) { if(x[k][b[k]]>=how[N*M/2]) { answer[k][b[k]]=i; b[k]--; break; } } a[j]++; } else { answer[j][b[j]]=i; for(k=j+1;k<N;k++) { if(x[k][a[k]]>=how[N*M/2]) { answer[k][a[k]]=i; a[k]++; break; } } b[j]--; } } } } allocate_tickets(answer); return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 768 KB | Output is correct |
5 | Correct | 2 ms | 2304 KB | Output is correct |
6 | Correct | 30 ms | 15788 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 0 ms | 384 KB | Output is correct |
4 | Correct | 3 ms | 1024 KB | Output is correct |
5 | Correct | 37 ms | 5108 KB | Output is correct |
6 | Correct | 797 ms | 84004 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 256 KB | Ticket 0 of color 3 is played on invalid day 3 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 416 KB | There is no ticket of color 1 on day 1 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 256 KB | There is no ticket of color 1 on day 1 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 256 KB | There is no ticket of color 1 on day 1 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 768 KB | Output is correct |
5 | Correct | 2 ms | 2304 KB | Output is correct |
6 | Correct | 30 ms | 15788 KB | Output is correct |
7 | Correct | 0 ms | 384 KB | Output is correct |
8 | Correct | 1 ms | 384 KB | Output is correct |
9 | Correct | 0 ms | 384 KB | Output is correct |
10 | Correct | 3 ms | 1024 KB | Output is correct |
11 | Correct | 37 ms | 5108 KB | Output is correct |
12 | Correct | 797 ms | 84004 KB | Output is correct |
13 | Incorrect | 1 ms | 256 KB | Ticket 0 of color 3 is played on invalid day 3 |
14 | Halted | 0 ms | 0 KB | - |