Submission #1004654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004654		zh_h	Art Exhibition (JOI18_art)	C++17	100 / 100	785 ms	21004 KiB

art

#include <bits/stdc++.h>
#define lint long long int
#define pb push_back
using namespace std;



int main(){

    lint n;
    cin >> n;
    vector<pair<lint, lint>> v;
    for(lint i = 0; i < n; i ++){
        lint temp1, temp2;
        cin >> temp1 >> temp2;
        v.pb({temp1, temp2});
    }
    sort(v.begin(), v.end());

    // cout << endl;
    // for(auto i : v){
        // cout << i.first << " " << i.second << endl;
    // }
    // cout << endl;

    lint curSUM = v[0].second;
    lint globalSUM = v[0].second;
    lint curMAX = v[0].first, curMIN = v[0].first;
    // int globalMAX = v[0].second, globalMIN = v[0].second;
    lint EndIndex;

    // cout << curSUM << " " << globalSUM << endl;
    for(int i = 1; i < n; i ++){
        // curSUM = max(v[i], curSUM + v[i]);
        
        if(v[i].second > (curSUM + v[i].second - v[i].first + curMAX)){ //* what about the equal case?
            curSUM = v[i].second;
            curMIN = v[i].first;
            curMAX = v[i].first;
        }
        else{
            curSUM += (v[i].second-v[i].first+curMAX);
            curMAX = v[i].first;
        }

        if(curSUM > globalSUM){
            globalSUM = curSUM;
            EndIndex = i;
        }

        // cout << curSUM << " " << globalSUM << endl;
    }

    cout << globalSUM;

    // lint StartIndex = EndIndex;

    // while(true){
    //     globalSUM -= v[StartIndex].second;
    //     if(globalSUM == 0){break;}
    //     StartIndex--;
    // }


    
    // cout << endl;
    // cout << StartIndex << " " << EndIndex;

    // int n;
    // cin >> n;
    // vector<int> v;
    // for(int i = 0; i < n; i ++){
    //     int temp;
    //     cin >> temp;
    //     v.pb(temp);
    // }

    // int curMax = v[0], globalMax = v[0], EndIndex;

    // for(int i = 1; i < n; i ++){
    //     curMax = max(v[i], v[i] + curMax);

    //     if(curMax > globalMax){
    //         globalMax = curMax;
    //         EndIndex = i;
    //     }
    // }
    // // cout << "globalMax = " << globalMax << endl;
    // int StartIndex = EndIndex;
    // // cout << StartIndex << endl;
    // while(globalMax > 0){
    //     // cout << StartIndex << " " << globalMax << " ";
    //     globalMax -= v[StartIndex];
    //     // cout << globalMax << endl;
    //     StartIndex--;
    // }
    // // cout << endl;
    // StartIndex++;

    // for(int i = StartIndex; i <= EndIndex; i ++){
    //     cout << v[i] << " ";
    // }
    // cout << endl;

}

Compilation message (stderr)

art.cpp: In function 'int main()':
art.cpp:28:31: warning: variable 'curMIN' set but not used [-Wunused-but-set-variable]
   28 |     lint curMAX = v[0].first, curMIN = v[0].first;
      |                               ^~~~~~
art.cpp:30:10: warning: variable 'EndIndex' set but not used [-Wunused-but-set-variable]
   30 |     lint EndIndex;
      |          ^~~~~~~~

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