oj.uz

Submission #169440

# Submission time Handle Problem Language Result Execution time Memory
169440 2019-12-20T10:57:32 Z Ruxandra985 Sure Bet (CEOI17_sure) C++14
20 / 100
 2 ms 380 KB 
/// pe langa faptul ca sunt inteligenta si nu stiu sa citesc enunturi
/// cateodata mai si uit sa trec pe standard input/output si iau 0 degeaba:)
#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
double v[DIMN],w[DIMN] , spv[DIMN] , spw[DIMN];
double check (int x , int y){
    return min(spv[x] - x - y , spw[y] - x - y);
}
int main()
{
    FILE *fin = stdin;
    int n , i , j , taken = 0 , st , dr , mid , nr;
    double sol = 0.0 ,x , y, z ,sx , sy;
    fscanf (fin,"%d",&n);
    for (i=1;i<=n;i++){
        fscanf (fin,"%lf%lf",&v[i],&w[i]);
    }
    sort (v+1 , v + n + 1);
    sort (w+1 , w + n + 1);

    for (i=1;i<=n-i+1;i++){
        swap(v[i] , v[n-i+1]);
        swap(w[i] , w[n-i+1]);
    }

    for (i=1;i<=n;i++){
        spv[i] = spv[i-1] + v[i];
        spw[i] = spw[i-1] + w[i];
    }
    spv[0] = spw[0] = -2000000000;
    spv[n+1] = spw[n+1] = 2000000000;
    for (i=1;i<=n;i++){
        /// avem spv[i]

        /// pot sa caut ternar sol pe w

        st = 1;
        dr = n;
        nr = 100;
        while (st <= dr && nr){
            mid = (st + dr)/2;
            x = check(i , mid-1);
            y = check(i , mid);
            z = check(i , mid+1);
            if (x <= y && y >= z){ /// solutie
                sol = max(sol , min(spv[i] - i - mid , spw[mid] - i - mid));
                st = mid;
            }
            else if (x <= y && y <= z)
                st = mid;
            else dr = mid;
            nr--;
        }
        sol = max(sol , min(spv[i] - i - mid , spw[mid] - i - mid));
    }

    /*sx = 0.0;
    for (i=1;i<=n;i++){
        sx += v[n-i+1];
        taken = 0;
        sy = 0.0;
        for (j=n;j;j--){
            sy += w[j];
            taken++;
            if (sol < min(sx - i - taken , sy - i - taken)){
                sol = min(sx - i - taken , sy - i - taken);
                printf ("%d %d\n" ,i , j);
            }
        }
    }*/

    cout << setprecision(4) << fixed << sol;
    return 0;
}

Compilation message

sure.cpp: In function 'int main()':
sure.cpp:13:17: warning: unused variable 'j' [-Wunused-variable]
     int n , i , j , taken = 0 , st , dr , mid , nr;
                 ^
sure.cpp:13:21: warning: unused variable 'taken' [-Wunused-variable]
     int n , i , j , taken = 0 , st , dr , mid , nr;
                     ^~~~~
sure.cpp:14:33: warning: unused variable 'sx' [-Wunused-variable]
     double sol = 0.0 ,x , y, z ,sx , sy;
                                 ^~
sure.cpp:14:38: warning: unused variable 'sy' [-Wunused-variable]
     double sol = 0.0 ,x , y, z ,sx , sy;
                                      ^~
sure.cpp:15:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d",&n);
     ~~~~~~~^~~~~~~~~~~~~
sure.cpp:17:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%lf%lf",&v[i],&w[i]);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Incorrect 2 ms 376 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Incorrect 2 ms 376 KB Output isn't correct
12 Halted 0 ms 0 KB -