Submission #696801

#	Time	Username	Problem	Language	Result	Execution time	Memory
696801		DJeniUp	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	3104 ms	435660 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;
#define fr first
#define sc second

map<ll,ll>mp[1507];

vector<vector<int> >ans;

priority_queue<pairll>q;

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;
        for(int i=1;i<=n;i++){
            vector<int>ro;
            ll a=0;
            for(int j=0;j<m;j++){
                res+=x[i-1][j];
                ro.push_back(-1);
            }
            
            q.push({-x[i-1][0],i});
        }
        for(int i=1;i<=(n*m)/2;i++){
            ll m1=q.top().fr;
            ll m2=q.top().sc;
            rs[m2]++;
            q.pop();
            res+=m1*2;
            if(rs[m2]<m)q.push({-x[m2-1][rs[m2]],m2});
        }
        
        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:29:16: warning: unused variable 'a' [-Wunused-variable]
   29 |             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