Submission #625346

#	Time	Username	Problem	Language	Result	Execution time	Memory
625346		Stavab	Art Exhibition (JOI18_art)	C++14	0 / 100	120 ms	262144 KiB

art

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

vector<pair<long long, long long>> v;
long long best, answer = 0;
int ind;

int d(int j)
{
    long long s = 0;
    long long curMin = v[j].first;
    best = 0;
    for(int i = j; i < v.size(); i++)
    {
        s += v[i].second;
        
        long long cur = s + curMin - v[i].first;
        if(best <= cur)
        {
            best = s + curMin - v[i].first;
            ind = i;
        }
    }
    
    s = 0;
    for(int i = j; i <= ind; i++)
    {
        answer = max(answer, best - s + v[i].first - curMin);
        
        s += v[i].second;
    }
    
    if(ind != v.size() - 1)
        d(ind + 1);
}

int main()
{
    int n;
    scanf("%d", &n);
    
    v.assign(n, pair<int, int>());
    for(int i = 0; i < n; i++)
    {
        scanf("%lld", &v[i].first);
        scanf("%lld", &v[i].second);
    }
    
    sort(v.begin(), v.end());
    
    d(0);
    
    printf("%lld\n", answer);
    
    return 0;
}

Compilation message (stderr)

art.cpp: In function 'int d(int)':
art.cpp:17:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i = j; i < v.size(); i++)
      |                    ~~^~~~~~~~~~
art.cpp:37:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     if(ind != v.size() - 1)
      |        ~~~~^~~~~~~~~~~~~~~
art.cpp:39:1: warning: no return statement in function returning non-void [-Wreturn-type]
   39 | }
      | ^
art.cpp: In function 'int main()':
art.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
art.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         scanf("%lld", &v[i].first);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
art.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         scanf("%lld", &v[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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