Submission #363267

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
363267	2021-02-05T12:10:45 Z	Ruxandra985	Schools (IZhO13_school)	C++14	100 / 100	306 ms	18668 KB

school

#include <bits/stdc++.h>
#define DIMN 300010
using namespace std;
int x[DIMN] , y[DIMN];
long long prefix[DIMN] , sufix[DIMN];
pair <int , int> v[DIMN];
multiset <int> w ;
int cmp (pair <int , int> a , pair <int , int> b){
    return a > b;
}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , m , s , i;
    long long suma , sol = 0;
    multiset<int> :: iterator it , it2;
    fscanf (fin,"%d%d%d",&n,&m,&s);
    for (i = 1 ; i <= n ; i++){
        fscanf (fin,"%d%d",&x[i],&y[i]);

        v[i] = make_pair(x[i] - y[i] , i);

    }

    sort (v + 1 , v + n + 1 , cmp);
    /// v = ordinea prioritatilor

    suma = 0;

    for (i = 1 ; i <= m ; i++){
        suma += x[v[i].second];
        w.insert(x[v[i].second]);
        prefix[i] = suma;
    }

    for (i = m + 1 ; i <= n ; i++){
        prefix[i - 1] = suma;
        w.insert(x[v[i].second]);
        suma += x[v[i].second];

        suma = suma - *w.begin();
        w.erase(w.begin());

    }

    prefix[n] = suma;

    /// ------------------------------------------------------------------
    w.clear();

    suma = 0;

    for (i = n ; n - i + 1 <= s ; i--){
        suma += y[v[i].second];
        w.insert(y[v[i].second]);
        sufix[i] = suma;
    }

    for (i = n - s ; i ; i--){
        sufix[i + 1] = suma;
        w.insert(y[v[i].second]);
        suma += y[v[i].second];

        suma = suma - *w.begin();
        w.erase(w.begin());

    }
    sufix[1] = suma;

    for (i = 0 ; i <= n ; i++){

        sol = max(sol , prefix[i] + sufix[i + 1]);

    }

    fprintf (fout,"%lld",sol);
    return 0;
}

Compilation message

school.cpp: In function 'int main()':
school.cpp:18:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   18 |     fscanf (fin,"%d%d%d",&n,&m,&s);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
school.cpp:20:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 |         fscanf (fin,"%d%d",&x[i],&y[i]);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	3 ms	620 KB	Output is correct
8	Correct	4 ms	748 KB	Output is correct
9	Correct	5 ms	748 KB	Output is correct
10	Correct	3 ms	748 KB	Output is correct
11	Correct	4 ms	748 KB	Output is correct
12	Correct	4 ms	748 KB	Output is correct
13	Correct	27 ms	3308 KB	Output is correct
14	Correct	48 ms	4716 KB	Output is correct
15	Correct	79 ms	7424 KB	Output is correct
16	Correct	200 ms	15468 KB	Output is correct
17	Correct	218 ms	14804 KB	Output is correct
18	Correct	239 ms	15084 KB	Output is correct
19	Correct	256 ms	16364 KB	Output is correct
20	Correct	306 ms	18668 KB	Output is correct