Submission #696787

#	Time	Username	Problem	Language	Result	Execution time	Memory
696787		DJeniUp	Carnival Tickets (IOI20_tickets)	C++17	12 / 100	3097 ms	480100 KiB

tickets

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

using namespace std;

typedef long long ll;
#define INF 100000000000007

ll r[307][90307],rs[307];

map<ll,ll>mp[307];

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();
    for(int i=0;i<=90000;i++){
        r[0][i]=-INF;
    }
    r[0][4500]=0;
    for(int i=1;i<=n;i++){
        vector<int>ro;
        ll a=0;
        for(int j=0;j<=90300;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(0,4500-i*k);j1<=min(9000,4500+i*k);j1++){
                if(j1-j>=0)r[i][j1]=max(r[i-1][j1-j]+mp[i][j],r[i][j1]);
            }
        }
    }
    ll y=4500;
    ll s=r[n][4500];
    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;
    }
    for(int i=0;i<n;i++){
       // for(int j=)
    }
    allocate_tickets(ans);
	return r[n][4500];
}

• Subtask 1: 0 / 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