Submission #696797

#	Time	Username	Problem	Language	Result	Execution time	Memory
696797		DJeniUp	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	3088 ms	435764 KiB

tickets

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

using namespace std;

typedef long long ll;
#define INF 100000000000007
typedef pair<int,int>pairll;

map<ll,ll>mp[1507];

vector<vector<int> >ans;

pairll d[2300007];

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	ll n = x.size();
	ll m = x[0].size();
    ll to=n*k*4;
    ll k1=n*k*2;
    ll rs[n+7];
    if(k==m && m!=1){
        ll res=0;
        ll h=0;
        for(int i=1;i<=n;i++){
            vector<int>ro;
            ll a=0;
            for(int j=0;j<m;j++){
                h++;
                d[h]={-x[i-1][j],i};
                res+=x[i-1][j];
                ro.push_back(-1);
            }
        }
        sort(d+1,d+1+h);
        for(int i=1;i<=(n*m)/2;i++){
            res+=d[i].first*2;
            rs[d[i].second]++;
        }
        
        ll l=0;
        for(int i=n;i>=1;i--){
            
            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 res;
        
    }
    ll r[n+7][to+307];
    for(int i=0;i<=to+300;i++){
        r[0][i]=-INF;
    }
    r[0][k1]=0;
    for(int i=1;i<=n;i++){
        vector<int>ro;
        ll a=0;
        for(int j=0;j<=to+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,k1-i*k);j1<=min(to,k1+i*k);j1++){
                if(j1-j>=0)r[i][j1]=max(r[i-1][j1-j]+mp[i][j],r[i][j1]);
            }
        }
    }
    ll y=k1;
    ll s=r[n][k1];
    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][k1];
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:28:16: warning: unused variable 'a' [-Wunused-variable]
   28 |             ll a=0;
      |                ^

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