Submission #1020633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020633		vjudge1	Shortcut (IOI16_shortcut)	C++17	31 / 100	2023 ms	604 KiB

shortcut

#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ll long long
#define pb push_back


ll b[200100];

long long find_shortcut(int n, vector<int> dl, vector<int> d, int c)
{
    ll ans = 4e18;
    for(int l=0; l<n; l++){
        for(int r=l+1; r<n; r++){
            ll sum = 0;
            b[l] = 0;
            for(int i=l; i>=0; i--){
                b[l] = max(b[l], sum + d[i]);
                if(i > 0) sum += dl[i-1];
            }
            b[r] = 0;
            sum = 0;
            for(int i=r; i<n; i++){
                b[r] = max(b[r], sum + d[i]);
                if(i < n - 1) sum += dl[i];
            }
            for(int i=l + 1; i<=r-1; i++){
                b[i] = d[i];
            }
            sum = c;
            for(int i=l; i<r; i++){
                sum += dl[i];
            }
            //cout<<l<<' '<<r<<' '<<sum<<'\n';
            //for(int i=l; i<=r; i++){
            //    cout<<b[i]<<' ';
            //}
            //cout<<"\n___________________\n";
            ll res = 0;
            for(int i=l; i<=r; i++){
                ll dsum = 0;
                for(int j=i-1; j>=l; j--){
                    dsum += dl[j];
                    res = max(res, min(dsum, sum - dsum) + b[i] + b[j]);
                }
            }
            for(int i=0; i<=l; i++){
                ll dsum = 0;
                for(int j=i-1; j>=0; j--){
                    dsum += dl[j];
                    res = max(res, dsum + d[i] + d[j]);
                }
            }
            for(int i=r; i<n; i++){
                ll dsum = 0;
                for(int j=i-1; j>=r; j--){
                    dsum += dl[j];
                    res = max(res, dsum + d[i] + d[j]);
                }
            }
            ans = min(ans, res);
        }
    }
    return ans;

            
}

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3