# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1057261 |
2024-08-13T16:04:48 Z |
Faisal_Saqib |
Teams (IOI15_teams) |
C++17 |
|
400 ms |
167508 KB |
#pragma optimize("O2")
#include <bits/stdc++.h>
// #include "teams.h"
using namespace std;
const int N=5e5+1;
#define lc second.first
#define rc second.second
#define sum first
pair<int,pair<int,int>> seg[50000001];
int nfi=0;
int build(int l,int&r)
{
int cur=nfi;
seg[cur].sum=0;
nfi++;
if(l==r)
return cur;
int mid=(l+r)/2;
seg[cur].lc=build(l,mid);
seg[cur].rc=build(mid+1,r);
return cur;
}
// node =def= seg[node] is being changed
// l,r are the range of seg[node](current segment)
// x is the index to be update
int update(int&node,int l,int&r,int&x)
{
int cur=nfi;
nfi++;
seg[cur]=seg[node];
if(l==r)
{
seg[cur].sum++;
return cur;
}
int mid=(l+r)/2;
if(x<=mid)
seg[cur].lc=update(seg[cur].lc,l,mid,x);
else
seg[cur].rc=update(seg[cur].rc,mid+1,r,x);
seg[cur].sum=seg[seg[cur].lc].sum+seg[seg[cur].rc].sum;
return cur;
}
int get(int&node,int l,int&r,int&ql,int&qr)
{
if(ql<=l and r<=qr)
return seg[node].sum;
int mid=(l+r)/2;
if(qr<=mid)
return get(seg[node].lc,l,mid,ql,qr);
else if(mid<ql)
return get(seg[node].rc,mid+1,r,ql,qr);
else
return get(seg[node].lc,l,mid,ql,qr)+get(seg[node].rc,mid+1,r,ql,qr);
}
int n,till[N],cup;
vector<int> add[N];
void init(int Ng, int A[], int B[])
{
n=Ng;
for(int i=0;i<n;i++)
{
add[A[i]].push_back(B[i]);
}
till[0]=build(1,n);
cup=till[0];
for(int i=1;i<=n;i++)
{
for(auto&j:add[i])
cup=update(cup,1,n,j);
till[i]=cup;
}
}
int Contains(int&l,int&r)
{
return get(till[l],1,n,r,n);
}
int cnt[N]; // cnt of x
int dp[N];// dp
int can(int m, int k[])
{
int sm=0;
for(int i=0;i<m;i++)
{
sm+=k[i];
if(sm>n)
{
//Not Possible
return 0;
}
}
for(int i=0;i<m;i++)
cnt[k[i]]++;
sort(k,k+m);
int mp=unique(k,k+m)-k;
//Here we write the dp solution
int mi=1e9;
for(int i=0;i<mp;i++)
{
int x=k[i];
int sz=cnt[x]*x;
int cntx=Contains(x,x);
dp[i]=cntx-sz;
for(int j=i-1;j>=i-7 and j>=0;j--)
dp[i]=min(dp[i],dp[j] + cntx - Contains(k[j],x) - sz);
mi=min(mi,dp[i]);
}
for(int i=0;i<mp;i++)
cnt[k[i]]=0;
return (mi>=0);
}
Compilation message
teams.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
1 | #pragma optimize("O2")
|
teams.cpp: In function 'int can(int, int*)':
teams.cpp:99:25: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
99 | int mp=unique(k,k+m)-k;
| ~~~~~~~~~~~~~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
18780 KB |
Output is correct |
2 |
Correct |
2 ms |
18780 KB |
Output is correct |
3 |
Correct |
2 ms |
18780 KB |
Output is correct |
4 |
Correct |
2 ms |
18780 KB |
Output is correct |
5 |
Correct |
2 ms |
18780 KB |
Output is correct |
6 |
Correct |
2 ms |
16732 KB |
Output is correct |
7 |
Correct |
2 ms |
18780 KB |
Output is correct |
8 |
Correct |
2 ms |
18780 KB |
Output is correct |
9 |
Correct |
2 ms |
18780 KB |
Output is correct |
10 |
Correct |
2 ms |
18780 KB |
Output is correct |
11 |
Correct |
3 ms |
18780 KB |
Output is correct |
12 |
Correct |
2 ms |
18780 KB |
Output is correct |
13 |
Correct |
2 ms |
18780 KB |
Output is correct |
14 |
Correct |
2 ms |
18780 KB |
Output is correct |
15 |
Correct |
2 ms |
18780 KB |
Output is correct |
16 |
Correct |
2 ms |
18776 KB |
Output is correct |
17 |
Correct |
2 ms |
18776 KB |
Output is correct |
18 |
Correct |
2 ms |
18780 KB |
Output is correct |
19 |
Correct |
2 ms |
18780 KB |
Output is correct |
20 |
Correct |
2 ms |
18780 KB |
Output is correct |
21 |
Correct |
2 ms |
18780 KB |
Output is correct |
22 |
Correct |
2 ms |
18780 KB |
Output is correct |
23 |
Correct |
2 ms |
18780 KB |
Output is correct |
24 |
Correct |
2 ms |
18780 KB |
Output is correct |
25 |
Correct |
2 ms |
18780 KB |
Output is correct |
26 |
Correct |
2 ms |
18792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
43864 KB |
Output is correct |
2 |
Correct |
32 ms |
43860 KB |
Output is correct |
3 |
Correct |
31 ms |
41820 KB |
Output is correct |
4 |
Correct |
32 ms |
44296 KB |
Output is correct |
5 |
Correct |
19 ms |
42844 KB |
Output is correct |
6 |
Correct |
18 ms |
42884 KB |
Output is correct |
7 |
Correct |
18 ms |
42844 KB |
Output is correct |
8 |
Correct |
18 ms |
42704 KB |
Output is correct |
9 |
Correct |
18 ms |
42708 KB |
Output is correct |
10 |
Correct |
17 ms |
42708 KB |
Output is correct |
11 |
Correct |
17 ms |
42704 KB |
Output is correct |
12 |
Correct |
17 ms |
42708 KB |
Output is correct |
13 |
Correct |
21 ms |
42980 KB |
Output is correct |
14 |
Correct |
24 ms |
41020 KB |
Output is correct |
15 |
Correct |
30 ms |
43888 KB |
Output is correct |
16 |
Correct |
29 ms |
43864 KB |
Output is correct |
17 |
Correct |
22 ms |
42844 KB |
Output is correct |
18 |
Correct |
20 ms |
42836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
94 ms |
44376 KB |
Output is correct |
2 |
Correct |
93 ms |
44372 KB |
Output is correct |
3 |
Correct |
57 ms |
47188 KB |
Output is correct |
4 |
Correct |
32 ms |
44368 KB |
Output is correct |
5 |
Correct |
81 ms |
43204 KB |
Output is correct |
6 |
Correct |
80 ms |
43092 KB |
Output is correct |
7 |
Correct |
81 ms |
43348 KB |
Output is correct |
8 |
Correct |
79 ms |
43092 KB |
Output is correct |
9 |
Correct |
18 ms |
42708 KB |
Output is correct |
10 |
Correct |
19 ms |
42964 KB |
Output is correct |
11 |
Correct |
24 ms |
43044 KB |
Output is correct |
12 |
Correct |
73 ms |
42892 KB |
Output is correct |
13 |
Correct |
81 ms |
43212 KB |
Output is correct |
14 |
Correct |
65 ms |
45592 KB |
Output is correct |
15 |
Correct |
69 ms |
44404 KB |
Output is correct |
16 |
Correct |
67 ms |
44372 KB |
Output is correct |
17 |
Correct |
58 ms |
43088 KB |
Output is correct |
18 |
Correct |
51 ms |
42960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
400 ms |
161860 KB |
Output is correct |
2 |
Correct |
389 ms |
161872 KB |
Output is correct |
3 |
Correct |
359 ms |
167508 KB |
Output is correct |
4 |
Correct |
242 ms |
161640 KB |
Output is correct |
5 |
Correct |
225 ms |
155732 KB |
Output is correct |
6 |
Correct |
229 ms |
155732 KB |
Output is correct |
7 |
Correct |
235 ms |
155732 KB |
Output is correct |
8 |
Correct |
225 ms |
155832 KB |
Output is correct |
9 |
Correct |
84 ms |
148416 KB |
Output is correct |
10 |
Correct |
101 ms |
154632 KB |
Output is correct |
11 |
Correct |
139 ms |
154816 KB |
Output is correct |
12 |
Correct |
225 ms |
155032 KB |
Output is correct |
13 |
Correct |
278 ms |
156488 KB |
Output is correct |
14 |
Correct |
360 ms |
161388 KB |
Output is correct |
15 |
Correct |
285 ms |
160328 KB |
Output is correct |
16 |
Correct |
331 ms |
160340 KB |
Output is correct |
17 |
Correct |
195 ms |
155252 KB |
Output is correct |
18 |
Correct |
181 ms |
155064 KB |
Output is correct |