Submission #89125

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
89125	2018-12-10T10:53:46 Z	Lkvatashidze	Schools (IZhO13_school)	C++17	15 / 100	176 ms	19524 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 ansp=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; ll ans=0;

  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 << max(ans0,ansp);

       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	500 KB	Output is correct
3	Correct	2 ms	580 KB	Output is correct
4	Incorrect	2 ms	600 KB	Output isn't correct
5	Incorrect	2 ms	600 KB	Output isn't correct
6	Incorrect	2 ms	600 KB	Output isn't correct
7	Incorrect	4 ms	772 KB	Output isn't correct
8	Incorrect	4 ms	772 KB	Output isn't correct
9	Incorrect	4 ms	788 KB	Output isn't correct
10	Incorrect	4 ms	788 KB	Output isn't correct
11	Incorrect	5 ms	916 KB	Output isn't correct
12	Incorrect	5 ms	932 KB	Output isn't correct
13	Incorrect	22 ms	2812 KB	Output isn't correct
14	Incorrect	48 ms	5572 KB	Output isn't correct
15	Incorrect	96 ms	10692 KB	Output isn't correct
16	Incorrect	109 ms	12032 KB	Output isn't correct
17	Incorrect	134 ms	14408 KB	Output isn't correct
18	Incorrect	148 ms	15948 KB	Output isn't correct
19	Incorrect	155 ms	17180 KB	Output isn't correct
20	Incorrect	176 ms	19524 KB	Output isn't correct