제출 #1251778

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251778		mngoc._.	Art Exhibition (JOI18_art)	C++20	100 / 100	238 ms	20412 KiB

art

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FOD(i, r, l) for (int i = (r), _l = (l); i >= _l; i--)
#define pii pair<int,int>
#define endl '\n'
#define pb push_back
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define Konosuba tuple<int , int , int, int>
#define fi first
#define se second


const int N = 5e5 + 5;
const int MOD = 1e9 + 7;
const int block = 330;
const int LOG = 30;
const int MAXN = 1e6 + 1;
const int INF = 1e14;
const int base = 311;


template<class A, class B>
bool umin(A& var, const B& val){ return (val < var) ? (var = val, true) : false; }
template<class A, class B>
bool umax(A& var, const B& val){ return (var < val) ? (var = val, true) : false; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class X, class Y> int random(const int& l, const int& r) {
  return uniform_int_distribution<int>(l,r)(rng);
}
int n;
pii a[N];
int b[N];
int prefixsum[N];
int st[4 * N];
void update(int idx , int l , int r , int pos , int val){
	if(l > pos || r < pos) return;
	if(l == r){
		st[idx] = val;
		return;
	}
    int mid = (l + r) / 2;
    update(2 * idx , l , mid , pos ,val);
    update(2 * idx + 1 , mid + 1 , r , pos ,val);
    st[idx] = max(st[2 * idx] , st[2 * idx + 1]);
}

int get(int idx , int l , int r , int u , int v){
	if(l > v || r < u) return 0;
	if(u <= l && r <= v){
		return st[idx];
	}
	int mid = (l + r) / 2;
	return max(get(2 * idx , l , mid , u , v) , get(2 * idx + 1 , mid + 1 , r , u , v));
}

void solve(void){
    cin >> n;
    FOR(i , 1 , n) cin >> a[i].first >> a[i].second;
    sort(a + 1 , a + n + 1);
    int res = 0;
    update(1 , 0 , n , 0 , a[1].first);
    FOR(i , 1 , n){
    	prefixsum[i] =  prefixsum[i - 1] + a[i].second;
    	int ans = get(1 , 0 , n , 0 , i - 1) + prefixsum[i] - a[i].first;
    	//cout << get(1 , 0 , n , 0 , i - 1) << endLL 
    	res = max(res , ans);
    	update(1 , 0 , n , i , a[i + 1].first - prefixsum[i]);
	}
	cout << res;
	
	
}


signed main(void) {
    if (fopen("smod.INP", "r")) {
        freopen("smod.INP", "r", stdin);
        freopen("smod.OUT", "w", stdout);
    } 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int testCase = 1; //cin >> testCase;
    FOR(i , 1 , testCase){
        solve();
    }

    cerr << "Time elapsed: " << TIME << "s.\n";
    return (0);
}

컴파일 시 표준 에러 (stderr) 메시지

art.cpp: In function 'int main()':
art.cpp:80:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         freopen("smod.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
art.cpp:81:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         freopen("smod.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50