oj.uz

Submission #935335

# Submission time Handle Problem Language Result Execution time Memory
935335 2024-02-29T03:44:47 Z HuyQuang_re_Zero Meetings (IOI18_meetings) C++14
19 / 100
 539 ms 257360 KB 
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define maxn 100005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define IDB pair <db,int>
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x)
#include "meetings.h"
using namespace std;
const ll oo=round(1e18);
ll a[maxn],i,j,q,n,up[5005][5005],down[5005][5005];
vector <ll> minimum_costs(vector <int> h,vector <int> L,vector <int> R)
{
    for(int x:h) a[++n]=x;
    q=L.size();
    for(i=0;i<q;i++) L[i]++,R[i]++;
    vector <ll> res(q);
    if(n<=5000 && q<=5000)
    {
        for(i=1;i<=n;i++)
        {
            ll ma=0;
            for(j=i;j>=1;j--)
            {
                ma=max(ma,a[j]);
                down[i][j]=down[i][j+1]+ma;
            }

            ma=0;
            for(j=i;j<=n;j++)
            {
                ma=max(ma,a[j]);
                up[i][j]=up[i][j-1]+ma;
            }
        }

        for(i=0;i<q;i++)
        {
            int l=L[i],r=R[i];
            res[i]=oo;
            for(int u=l;u<=r;u++)
                res[i]=min(res[i],down[u][l]+up[u][r]-a[u]);
        }
    }
    return res;
}
/*
int main()
{
    freopen("meetings.inp","r",stdin);
    freopen("meetings.out","w",stdout);
    vector <int> a,L,R;
    int k,n,l,r;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>k,a.push_back(k);
    while(cin>>l>>r) L.push_back(l),R.push_back(r);
    vector <ll> res=minimum_costs(a,L,R);
    for(int x:res) cout<<x<<'\n';
}
*/

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 46 ms 110772 KB Output is correct
3 Correct 43 ms 110964 KB Output is correct
4 Correct 42 ms 110932 KB Output is correct
5 Correct 44 ms 110940 KB Output is correct
6 Correct 42 ms 110928 KB Output is correct
7 Correct 42 ms 110932 KB Output is correct
8 Correct 45 ms 110928 KB Output is correct
9 Correct 42 ms 110932 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 46 ms 110772 KB Output is correct
3 Correct 43 ms 110964 KB Output is correct
4 Correct 42 ms 110932 KB Output is correct
5 Correct 44 ms 110940 KB Output is correct
6 Correct 42 ms 110928 KB Output is correct
7 Correct 42 ms 110932 KB Output is correct
8 Correct 45 ms 110928 KB Output is correct
9 Correct 42 ms 110932 KB Output is correct
10 Correct 299 ms 257220 KB Output is correct
11 Correct 534 ms 257360 KB Output is correct
12 Correct 289 ms 257316 KB Output is correct
13 Correct 539 ms 257248 KB Output is correct
14 Correct 265 ms 257108 KB Output is correct
15 Correct 280 ms 257108 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 13 ms 2524 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 13 ms 2524 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 46 ms 110772 KB Output is correct
3 Correct 43 ms 110964 KB Output is correct
4 Correct 42 ms 110932 KB Output is correct
5 Correct 44 ms 110940 KB Output is correct
6 Correct 42 ms 110928 KB Output is correct
7 Correct 42 ms 110932 KB Output is correct
8 Correct 45 ms 110928 KB Output is correct
9 Correct 42 ms 110932 KB Output is correct
10 Correct 299 ms 257220 KB Output is correct
11 Correct 534 ms 257360 KB Output is correct
12 Correct 289 ms 257316 KB Output is correct
13 Correct 539 ms 257248 KB Output is correct
14 Correct 265 ms 257108 KB Output is correct
15 Correct 280 ms 257108 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Incorrect 13 ms 2524 KB Output isn't correct
18 Halted 0 ms 0 KB -