oj.uz

Submission #683740

# Submission time Handle Problem Language Result Execution time Memory
683740 2023-01-19T08:54:00 Z aSSSd Akcija (COCI21_akcija) C++14
10 / 110
 23 ms 32016 KB 
#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r)
{
    return l+rng()%(r-l+1);
}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define forinc(x,a,b) for(int x=a;x<=b;x++)
#define fordec(x,a,b) for(int x=a;x>=b;x--)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ll long long
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f,x) memset(f,x,sizeof(f))
#define getbit(x,i) ((x>>(i))&1)
#define batbit(x,i) (x|(1ll<<(i)))
#define tatbit(x,i) (x&~(1<<(i)))
#define gg exit(0);
#define int long long
#define ii pair<int,int>
const int N = 2010;
int n , k;
ii a[N];
int f[N][N];
main()
{
    fasty;
    cin >> n >> k;
    forinc(i,1,n)
    {
        cin >> a[i].fi >> a[i].se;
    }
    sort(a+1,a+n+1);
    if(k==1)
    {
        memset(f,127,sizeof f);
        int ngu=f[0][0];
        f[0][0]=0;
        forinc(i,0,n)
        {
            forinc(j,0,n) if(f[i][j] != ngu )
            {
                if(a[i+1].se>j)
                {
                    f[i+1][j+1] = min(f[i+1][j+1] , f[i][j] + a[i+1].fi);
                }
                f[i+1][j] = min(f[i+1][j] , f[i][j]);
            }
        }
        fordec(j,n,1)
        {
            if(f[n][j] != ngu)
            {
                cout << j <<" "<< f[n][j] << "\n";
                return 0;
            }
        }
    }
}

Compilation message

Main.cpp:31:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   31 | main()
      | ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31956 KB Output is correct
2 Correct 21 ms 32016 KB Output is correct
3 Correct 22 ms 31956 KB Output is correct
4 Correct 20 ms 31964 KB Output is correct
5 Correct 23 ms 31956 KB Output is correct
6 Correct 17 ms 31956 KB Output is correct
7 Correct 18 ms 32008 KB Output is correct
8 Correct 17 ms 31948 KB Output is correct
9 Correct 17 ms 31908 KB Output is correct
10 Correct 18 ms 31932 KB Output is correct
11 Correct 13 ms 31948 KB Output is correct
12 Correct 14 ms 31952 KB Output is correct
13 Correct 13 ms 31952 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31956 KB Output is correct
2 Correct 21 ms 32016 KB Output is correct
3 Correct 22 ms 31956 KB Output is correct
4 Correct 20 ms 31964 KB Output is correct
5 Correct 23 ms 31956 KB Output is correct
6 Correct 17 ms 31956 KB Output is correct
7 Correct 18 ms 32008 KB Output is correct
8 Correct 17 ms 31948 KB Output is correct
9 Correct 17 ms 31908 KB Output is correct
10 Correct 18 ms 31932 KB Output is correct
11 Correct 13 ms 31948 KB Output is correct
12 Correct 14 ms 31952 KB Output is correct
13 Correct 13 ms 31952 KB Output is correct
14 Incorrect 19 ms 31956 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31956 KB Output is correct
2 Correct 21 ms 32016 KB Output is correct
3 Correct 22 ms 31956 KB Output is correct
4 Correct 20 ms 31964 KB Output is correct
5 Correct 23 ms 31956 KB Output is correct
6 Correct 17 ms 31956 KB Output is correct
7 Correct 18 ms 32008 KB Output is correct
8 Correct 17 ms 31948 KB Output is correct
9 Correct 17 ms 31908 KB Output is correct
10 Correct 18 ms 31932 KB Output is correct
11 Correct 13 ms 31948 KB Output is correct
12 Correct 14 ms 31952 KB Output is correct
13 Correct 13 ms 31952 KB Output is correct
14 Incorrect 19 ms 31956 KB Output isn't correct
15 Halted 0 ms 0 KB -