Submission #414356

#	Time	Username	Problem	Language	Result	Execution time	Memory
414356		mosiashvililuka	Meetings (IOI18_meetings)	C++17	19 / 100	666 ms	234824 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
const long long inf=99999999999999999LL;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,f[750009],pas;
pair <long long, long long> Q[750009];
vector <long long> ANS;
long long Lf[5003][5003],Rg[5003][5003];
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    a=H.size();
    tes=L.size();
    for(i=1; i<=a; i++){
        f[i]=H[i-1];
    }
    for(t=1; t<=tes; t++){
        Q[t].first=L[t-1]+1;
        Q[t].second=R[t-1]+1;
    }
    if(a<=5000&&tes<=5000){
        for(i=1; i<=a; i++){
            zx=0;xc=0;
            for(j=i; j>=1; j--){
                if(xc<f[j]) xc=f[j];
                zx+=xc;
                Lf[i][j]=zx;
            }
        }
        for(i=1; i<=a; i++){
            zx=0;xc=0;
            for(j=i; j<=a; j++){
                if(xc<f[j]) xc=f[j];
                zx+=xc;
                Rg[i][j]=zx;
            }
        }
        for(t=1; t<=tes; t++){
            zx=inf;
            for(i=Q[t].first; i<=Q[t].second; i++){
                if(zx>Lf[i][Q[t].first]+Rg[i][Q[t].second]-f[i]){
                    zx=Lf[i][Q[t].first]+Rg[i][Q[t].second]-f[i];
                }
            }
            ANS.push_back(zx);
        }
        return ANS;
    }
    return ANS;
}
/*int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    vector <int> H,L,R;
    cin>>a>>tes;
    for(i=1; i<=a; i++){
        cin>>c;
        H.push_back(c);
    }
    for(t=1; t<=tes; t++){
        cin>>c>>d;
        L.push_back(c);
        R.push_back(d);
    }
    ANS=minimum_costs(H,L,R);
    for(t=0; t<ANS.size(); t++){
        cout<<ANS[t]<<" ";
    }
    return 0;
}*/

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40