oj.uz

Submission #1004406

# Submission time Handle Problem Language Result Execution time Memory
1004406 2024-06-21T08:40:12 Z CSQ31 Let's Win the Election (JOI22_ho_t3) C++17
21 / 100
 1504 ms 4956 KB 
#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
ld dp[555][555];
int main()
{
    owo
    int n,K;
    cin>>n>>K;
    vector<pii>t(n);
    vector<ld>a(n),b(n);
    for(int i=0;i<n;i++){
        cin>>t[i].fi>>t[i].se;
        if(t[i].se == -1)t[i].se = 1e9;
        swap(t[i].fi,t[i].se);
    } 
    sort(all(t));
    for(int i=0;i<n;i++){
        if(t[i].fi == 1e9)t[i].fi = -1;
        a[i] = t[i].se;
        b[i] = t[i].fi;
    }
    ld ans = 1e18;
    for(int k=0;k<K;k++){
        //cout<<k<<'\n';
        for(int i=0;i<n;i++){
            for(int j=0;j<=n;j++)dp[i][j] = 1e18;
        }
        dp[0][1] = a[0]/(k+1);
        if(b[0] != -1 && k)dp[0][0] = b[0];
        for(int i=1;i<n;i++){
            for(int j=0;j<=i+1;j++){
                int c = i+1 - j;

                if(b[i] != -1 && c<=k){ //add coord
                    dp[i][j] = min(dp[i][j],dp[i-1][j] + b[i]/c);
                }
                if(j){
                    dp[i][j] = min(dp[i][j],dp[i-1][j-1] + a[i]/(k+1));
                }
                
                if(c>k)dp[i][j] = min(dp[i][j],dp[i-1][j]);
                
            }
            
        }
        for(int i=K-1;i<n;i++){
            for(int j=0;j<=i+1;j++){
                 int c = min(k,i+1 - j);
                 if(c>= k && c+j >= K)ans = min(ans,dp[i][j]);
            }
        }
    }
    cout<<fixed<<setprecision(5)<<ans<<'\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 169 ms 4700 KB Output is correct
6 Correct 407 ms 4700 KB Output is correct
7 Correct 701 ms 4700 KB Output is correct
8 Correct 946 ms 4696 KB Output is correct
9 Correct 1129 ms 4696 KB Output is correct
10 Correct 868 ms 4804 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 169 ms 4700 KB Output is correct
6 Correct 407 ms 4700 KB Output is correct
7 Correct 701 ms 4700 KB Output is correct
8 Correct 946 ms 4696 KB Output is correct
9 Correct 1129 ms 4696 KB Output is correct
10 Correct 868 ms 4804 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 470 ms 4804 KB Output is correct
13 Correct 444 ms 4700 KB Output is correct
14 Correct 421 ms 4804 KB Output is correct
15 Correct 1020 ms 4948 KB Output is correct
16 Correct 1038 ms 4804 KB Output is correct
17 Correct 919 ms 4700 KB Output is correct
18 Correct 1421 ms 4804 KB Output is correct
19 Correct 1310 ms 4812 KB Output is correct
20 Correct 1373 ms 4700 KB Output is correct

Subtask #3
0 / 11.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 33.0

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

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1504 ms 4808 KB Output is correct
2 Correct 1410 ms 4956 KB Output is correct
3 Correct 1389 ms 4696 KB Output is correct
4 Correct 1418 ms 4812 KB Output is correct
5 Correct 1420 ms 4808 KB Output is correct
6 Correct 1311 ms 4804 KB Output is correct
7 Correct 1383 ms 4808 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 169 ms 4700 KB Output is correct
6 Correct 407 ms 4700 KB Output is correct
7 Correct 701 ms 4700 KB Output is correct
8 Correct 946 ms 4696 KB Output is correct
9 Correct 1129 ms 4696 KB Output is correct
10 Correct 868 ms 4804 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 470 ms 4804 KB Output is correct
13 Correct 444 ms 4700 KB Output is correct
14 Correct 421 ms 4804 KB Output is correct
15 Correct 1020 ms 4948 KB Output is correct
16 Correct 1038 ms 4804 KB Output is correct
17 Correct 919 ms 4700 KB Output is correct
18 Correct 1421 ms 4804 KB Output is correct
19 Correct 1310 ms 4812 KB Output is correct
20 Correct 1373 ms 4700 KB Output is correct
21 Incorrect 0 ms 348 KB Output isn't correct
22 Halted 0 ms 0 KB -