oj.uz

Submission #881726

# Submission time Handle Problem Language Result Execution time Memory
881726 2023-12-01T19:12:07 Z alexdd Schools (IZhO13_school) C++17
40 / 100
 2000 ms 5064 KB 
#include<bits/stdc++.h>
using namespace std;
const int NRIT = 4e5;
const int NRSHUFFLES = 100;
int n,m,s;
pair<int,pair<int,int>> v[300005];
int unde[300005];
mt19937 rnd(293123);
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>s;
    int a,b;
    for(int i=1;i<=n;i++)
    {
        cin>>a>>b;
        v[i] = {a-b,{a,b}};
    }
    sort(v+1,v+1+n);
    long long mxm=0;
    for(int pas2=0;pas2<NRSHUFFLES;pas2++)
    {
        for(int i=1;i<=n;i++)
            unde[i]=0;
        for(int i=1;i<=s;i++)
            unde[i]=2;
        for(int i=1;i<=m;i++)
            unde[n-i+1]=1;
        for(int pas=0;pas<NRIT;pas++)
        {
            int x = rnd()%n + 1;
            int y = rnd()%n + 1;
            if(unde[x]==unde[y])
                continue;
            if(unde[y]==0)
                swap(x,y);
            if(unde[x]==0)
            {
                if(unde[y]==1)
                {
                    if(v[x].second.first - v[y].second.first > 0)
                        swap(unde[x],unde[y]);
                }
                else
                {
                    if(v[x].second.second - v[y].second.second > 0)
                        swap(unde[x],unde[y]);
                }
            }
            else
            {
                if(unde[x]==2)
                    swap(x,y);
                if(v[x].second.second - v[x].second.first + v[y].second.first - v[y].second.second > 0)
                {
                    swap(unde[x],unde[y]);
                }
            }
        }
        long long sum=0;
        for(int i=1;i<=n;i++)
        {
            if(unde[i]==1)
                sum += v[i].second.first;
            else if(unde[i]==2)
                sum += v[i].second.second;
        }
        mxm=max(mxm,sum);
        random_shuffle(v+1,v+1+n);
    }
    cout<<mxm;
    return 0;
}

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1379 ms 2492 KB Output is correct
2 Correct 1070 ms 2492 KB Output is correct
3 Correct 1370 ms 2492 KB Output is correct
4 Correct 1443 ms 2488 KB Output is correct
5 Correct 1521 ms 2640 KB Output is correct
6 Correct 1381 ms 2492 KB Output is correct
7 Incorrect 1383 ms 2508 KB Output isn't correct
8 Correct 998 ms 2520 KB Output is correct
9 Incorrect 1183 ms 2512 KB Output isn't correct
10 Incorrect 1218 ms 2512 KB Output isn't correct
11 Incorrect 1365 ms 2516 KB Output isn't correct
12 Incorrect 1281 ms 2520 KB Output isn't correct
13 Incorrect 1206 ms 2648 KB Output isn't correct
14 Incorrect 1735 ms 2896 KB Output isn't correct
15 Incorrect 1254 ms 4952 KB Output isn't correct
16 Correct 1447 ms 4720 KB Output is correct
17 Execution timed out 2052 ms 4692 KB Time limit exceeded
18 Execution timed out 2012 ms 4688 KB Time limit exceeded
19 Execution timed out 2049 ms 4540 KB Time limit exceeded
20 Execution timed out 2056 ms 5064 KB Time limit exceeded