Submission #1049847

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049847		vjudge1	Art Exhibition (JOI18_art)	C++17	100 / 100	111 ms	20048 KiB

art

#include<bits/stdc++.h>
#define en "\n"
#define s second
#define f first
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define vi vector<int>
#define vii vector<pair<int,int>>
#define int long long
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define loop(a) for(int i = 0; i < a; i++)
#define loopv(i,a) for (int i = 0; i < a; i++)
#define all(x) (x).begin(), (x).end()
#define prDouble(x) printf("%.8f", x)
#define goog(tno) printf("Case #%d: ", tno)
using namespace std;
const int N = 500100;

void solve() {
    int n;
    cin>>n;
    vii a(n);
    for(int i=0; i<n; i++){
    	cin>>a[i].f>>a[i].s;
    }
    
    sort(all(a));
    for(int i=0; i<a.size()-1; i++){
    	if(a[i].f==a[i+1].f){
    		a[i+1].s+=a[i].s;
    		a.erase(a.begin()+i);
    		i--;
    	}
    }
    n=a.size();
    // for(int i=0; i<n; i++){
    	// cout<<a[i].f<<" "<<a[i].s<<en;	
    // }
    
    vi p(n+1, 0), pl(n+1, 0), pr(n+1, 0);
    for(int i=0; i<n; i++){
    	p[i+1] = p[i] + a[i].s;
    }
    for(int i=1; i<=n; i++){
    	pl[i] = a[i-1].f - p[i-1];
    }
    for(int i=1; i<=n; i++){
    	pr[i] = p[i] - a[i-1].f;
    }
    // for(int i=0; i<n; i++){
    	// cout<<a[i].f<<" "<<a[i].s<<" "<<p[i+1]<<" "<<pl[i+1]<<" "<<pr[i+1]<<en;
    // }
    // build(pl, 1, 0, n);
    int mx=0, mx2=0;
    int ans=0;
    for(int i=0; i<=n; i++){
    	mx = max(mx, pl[i]);
    	ans = max(ans, pr[i]+mx);
    }
    cout<<ans;
    
}

signed main() {
    fast_io;
    int tc = 1;
    // scanf("%d", &tc);
    while (tc--)
        solve();
}

Compilation message (stderr)

art.cpp: In function 'void solve()':
art.cpp:28:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i=0; i<a.size()-1; i++){
      |                  ~^~~~~~~~~~~
art.cpp:54:15: warning: unused variable 'mx2' [-Wunused-variable]
   54 |     int mx=0, mx2=0;
      |               ^~~

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