oj.uz

Submission #881727

# Submission time Handle Problem Language Result Execution time Memory
881727 2023-12-01T19:14:10 Z alexdd Schools (IZhO13_school) C++17
30 / 100
 2000 ms 5200 KB 
#include<bits/stdc++.h>
using namespace std;
const int NRIT = 4e5;
const int proba = 1000;
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 || rnd()%proba==0)
                        swap(unde[x],unde[y]);
                }
                else
                {
                    if(v[x].second.second - v[y].second.second > 0 || rnd()%proba==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 || rnd()%proba==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
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1521 ms 2496 KB Output is correct
2 Correct 1080 ms 2488 KB Output is correct
3 Correct 1481 ms 2492 KB Output is correct
4 Correct 1613 ms 2492 KB Output is correct
5 Correct 1709 ms 2488 KB Output is correct
6 Correct 1550 ms 2640 KB Output is correct
7 Incorrect 1543 ms 2512 KB Output isn't correct
8 Incorrect 1014 ms 2516 KB Output isn't correct
9 Incorrect 1305 ms 2512 KB Output isn't correct
10 Incorrect 1331 ms 2536 KB Output isn't correct
11 Incorrect 1495 ms 2516 KB Output isn't correct
12 Incorrect 1405 ms 2516 KB Output isn't correct
13 Incorrect 1268 ms 2764 KB Output isn't correct
14 Incorrect 1879 ms 2904 KB Output isn't correct
15 Incorrect 1269 ms 4716 KB Output isn't correct
16 Incorrect 1493 ms 4720 KB Output isn't correct
17 Execution timed out 2058 ms 4692 KB Time limit exceeded
18 Execution timed out 2095 ms 4564 KB Time limit exceeded
19 Execution timed out 2055 ms 4696 KB Time limit exceeded
20 Execution timed out 2072 ms 5200 KB Time limit exceeded