Submission #696791

#	Time	Username	Problem	Language	Result	Execution time	Memory
696791		DJeniUp	Carnival Tickets (IOI20_tickets)	C++17	23 / 100	3133 ms	2097152 KiB

tickets

#include "tickets.h"
#include "bits/stdc++.h"
#include <vector>

using namespace std;

typedef long long ll;
#define INF 100000000000007


map<ll,ll>mp[1507];

vector<vector<int> >ans;

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	ll n = x.size();
	ll m = x[0].size();
    //ll to=n*m*2;
    ll r[n+7][n*m*4+307],rs[n+7];
    for(int i=0;i<=n*m*2+300;i++){
        r[0][i]=-INF;
    }
    r[0][n*k*2]=0;
    for(int i=1;i<=n;i++){
        vector<int>ro;
        ll a=0;
        for(int j=0;j<=n*m*4+300;j++){
            r[i][j]=-INF;
        }
        for(int j=0;j<m;j++){
            
            ro.push_back(-1);
        }
        for(int j=0;j<k;j++){
            a-=x[i-1][j];
            
        }
        ans.push_back(ro);
        for(int j=k;j>=0;j--){
            mp[i][k-j-j]=a;
            if(j>0)a+=x[i-1][j-1]+x[i-1][m-1-(k-j)];
        }
        for(int j=-k;j<=k;j+=2){
            for(int j1=max(0ll,n*k*2-i*k);j1<=min(n*m*4,n*k*2+i*k);j1++){
                if(j1-j>=0)r[i][j1]=max(r[i-1][j1-j]+mp[i][j],r[i][j1]);
            }
        }
    }
    ll y=n*k*2;
    ll s=r[n][n*k*2];
    ll l=0;
    for(int i=n;i>=1;i--){
        for(int j=0;j<=k;j++){
            ll t=k-j*2;
            if(y-t>=0 && r[i-1][y-t]==s-mp[i][t]){
                rs[i]=j;
                s=r[i-1][y-t];
                y-=t;
                break;
            }
        }
        ll h=l;
        
        //cout<<i<<" "<<rs[i]<<endl;
        for(int j=0;j<rs[i];j++){
            ans[i-1][j]=(h%k);
            h++;
            //cout<<j<<" ";
        }
       // cout<<endl;
        l=h;
        for(int j=m-1;j>=m-(k-rs[i]);j--){
            ans[i-1][j]=(h%k);
            h++;
            //cout<<j<<" ";
        }
        //cout<<endl;
    }
    
    allocate_tickets(ans);
	return r[n][n*k*2];
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 12 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10