Submission #89124

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
89124	2018-12-10T10:52:39 Z	Lkvatashidze	Schools (IZhO13_school)	C++17	15 / 100	200 ms	19572 KB

school

#include <bits/stdc++.h>
#define ll long long
using namespace std;

  struct ABC {
    int sum, fir, sec, ind;
 };

   bool comp (ABC a, ABC b) {
      return a.sum>b.sum;
   }

   ll sol();
   ABC v[300005];
   pair < int, int > se[300005], fi[300005];
   bool used[300005];
   ll n, m, s;
   pair < ll, ll > a[300005];
   pair < ll, ll > b[300005];
    ll ans1, ans0;
 int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);


      cin >> n >> m >> s;

      ll ans=sol();

    for (int k=1; k<=n; k++) {
        cin >> v[k].fir;
        cin >> v[k].sec;
        fi[k].first=v[k].fir;
        fi[k].second=k;
        se[k].first=v[k].sec;
        se[k].second=k;
        a[k].first=v[k].fir;
        a[k].second=k;
        b[k].first=v[k].sec;
        b[k].second=k;
        v[k].ind=k;
        v[k].sum=v[k].fir+v[k].sec;
    }

    sort(v+1,v+1+n, comp);

        int k=1;

  while (k<n && s && m) {
        ans+=max(v[k].sec+v[k+1].fir,v[k].fir+v[k+1].sec);
        used[v[k].ind]=true;
        used[v[k+1].ind]=true;
        m--;
        s--;
        k+=2;
    }


     if (m==0) {
      sort(se+1,se+1+n);
      reverse(se+1,se+1+n);
      for (int i=1; i<=n; i++) {
            if (s==0) break;
        if (used[se[i].second]) continue;
        ans+=se[i].first;
        s--;
      }
       cout << ans;
       return 0;
  }
     if (s==0) {
      sort(fi+1,fi+1+n);
      reverse(fi+1,fi+1+n);
      for (int i=1; i<=n; i++) {
            if (m==0) break;
        if (used[fi[i].second]) continue;
        ans+=fi[i].first;
        m--;
      }
       cout << ans;
       return 0;
 }
    return 0;
}
 ll sol() {


    sort (a+1,a+1+n);
    sort (b+1,b+1+n);

    for (ll k=n; k>=n-m+1; k--) {
        ans1+=a[k].first;
        used[a[k].second]=true;
    }

    reverse(b+1,b+1+n);

    ll i=1; ll j=1;
     while (i<=s && j<=n) {
        if (used[b[j].second]) {
            j++;
            continue;
        }
        ans1+=b[j].first;
        used[b[j].second]=true;
        j++; i++;
     }

   for (ll k=1; k<=n; k++)
     used[k]=false;

    sort (a+1,a+1+n);
    sort (b+1,b+1+n);

    for (ll k=n; k>=n-s+1; k--) {
        ans0+=b[k].first;
        used[b[k].second]=true;
    }

    reverse(a+1,a+1+n);

     i=1; j=1;
     while (i<=m && j<=n) {
        if (used[a[j].second]) {
            j++;
            continue;
        }
        ans0+=a[j].first;
        used[b[j].second]=true;
        j++; i++;
     }

       return max(ans1,ans0);


}

Subtask #1

15.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	428 KB	Output is correct
3	Correct	2 ms	440 KB	Output is correct
4	Incorrect	3 ms	648 KB	Output isn't correct
5	Incorrect	2 ms	648 KB	Output isn't correct
6	Incorrect	2 ms	648 KB	Output isn't correct
7	Incorrect	5 ms	800 KB	Output isn't correct
8	Incorrect	4 ms	800 KB	Output isn't correct
9	Incorrect	6 ms	928 KB	Output isn't correct
10	Incorrect	5 ms	928 KB	Output isn't correct
11	Incorrect	5 ms	928 KB	Output isn't correct
12	Incorrect	5 ms	928 KB	Output isn't correct
13	Incorrect	23 ms	2924 KB	Output isn't correct
14	Incorrect	50 ms	5556 KB	Output isn't correct
15	Incorrect	100 ms	10732 KB	Output isn't correct
16	Incorrect	122 ms	12140 KB	Output isn't correct
17	Incorrect	138 ms	14572 KB	Output isn't correct
18	Incorrect	149 ms	15964 KB	Output isn't correct
19	Incorrect	166 ms	17276 KB	Output isn't correct
20	Incorrect	200 ms	19572 KB	Output isn't correct