oj.uz

Submission #881728

# Submission time Handle Problem Language Result Execution time Memory
881728 2023-12-01T19:16:10 Z alexdd Schools (IZhO13_school) C++17
40 / 100
 2000 ms 4948 KB 
#include<bits/stdc++.h>
using namespace std;
const int NRIT = 8e5;
const int NRSHUFFLES = 50;
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 2396 KB Output is correct
2 Correct 1070 ms 2392 KB Output is correct
3 Correct 1356 ms 2488 KB Output is correct
4 Correct 1423 ms 2640 KB Output is correct
5 Correct 1492 ms 2488 KB Output is correct
6 Correct 1381 ms 2492 KB Output is correct
7 Incorrect 1380 ms 2640 KB Output isn't correct
8 Correct 990 ms 2520 KB Output is correct
9 Incorrect 1181 ms 2516 KB Output isn't correct
10 Incorrect 1222 ms 2512 KB Output isn't correct
11 Incorrect 1338 ms 2644 KB Output isn't correct
12 Incorrect 1277 ms 2648 KB Output isn't correct
13 Incorrect 1163 ms 2652 KB Output isn't correct
14 Incorrect 1608 ms 2900 KB Output isn't correct
15 Incorrect 1119 ms 4716 KB Output isn't correct
16 Correct 1321 ms 4716 KB Output is correct
17 Incorrect 1830 ms 4716 KB Output isn't correct
18 Incorrect 1957 ms 4712 KB Output isn't correct
19 Incorrect 1951 ms 4712 KB Output isn't correct
20 Execution timed out 2054 ms 4948 KB Time limit exceeded