Submission #1109973

#TimeUsernameProblemLanguageResultExecution timeMemory
1109973whyalwaysmezzzArt Exhibition (JOI18_art)C++14
0 / 100
1 ms2384 KiB
#include <bits/stdc++.h> #define int long long #define fi first #define se second #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++) #define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--) #define BIT(mask,i) ((mask >> i) & 1ll ) #define endl '\n' #define all(x) x.begin(),x.end() #define ii pair <int,int> using namespace std; #define read doc() int doc () {bool minus = false;int result = 0;char ch;ch = getchar();while (true) {if (ch == '-') break;if (ch >= '0' && ch <= '9') break;ch = getchar();}if (ch == '-') minus = true; else result = ch-'0';while (true) {ch = getchar();if (ch < '0' || ch > '9') break;result = result*10 + (ch - '0');}if (minus)return -result;else return result;} template<class X, class Y>bool minimize(X &x, const Y &y) {if (x > y) {x = y;return true;} else return false;} template<class X, class Y>bool maximize(X &x, const Y &y) {if (x < y) {x = y;return true;} else return false;} const long long oo = 1e18; const int N = 1e6+5; const int MOD = 1e9+7; ii a[N]; int f[N]; int st[N*4]; void update(int id,int l,int r,int i,int val) { if ( l > i || r < i) return; if (l == r && r == i) { st[id] = val; return; } int m = l + r >> 1; update(id*2,l,m,i,val); update(id*2+1,m+1,r,i,val); st[id] = min(st[id*2] , st[id*2+1]); } int get(int id,int l,int r,int u,int v) { if ( l > v || r < u) return oo; if ( l >= u && r <= v ) return st[id]; int m = l + r >> 1; return min(get(id*2,l,m,u,v) , get(id*2+1,m+1,r,u,v)); } void Whyalwaysmezzz() { int n; cin >> n; // FOR(i,1,n) cin >> a[i]; FOR(i,1,n) { cin >> a[i].fi >> a[i].se; } sort(a+1,a+1+n); FOR(i,1,n) f[i] = f[i-1] + a[i].se; FOR(i,1,n) update(1,0,n,i,oo); int ans = 0; FOR(i,1,n) { int x = get(1,0,n,0,i-1); ans = max(ans,f[i] - a[i].fi - x); update(1,0,n,i,f[i-1] - a[i].fi); } cout << ans; return; } #define TASK "task" signed main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);//freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout); int Sty1e = 1; // cin >> Sty1e; while (Sty1e--) Whyalwaysmezzz(); return 0; }

Compilation message (stderr)

art.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int)':
art.cpp:30:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |  int m = l + r >> 1;
      |          ~~^~~
art.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int)':
art.cpp:39:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |  int m = l + r >> 1;
      |          ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...