oj.uz

답안 #440592

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
440592 2021-07-02T13:49:46 Z yungyao Palembang Bridges (APIO15_bridge) C++17
22 / 100
 62 ms 12456 KB 
/*

weak        weak  we      ak   we  akwea        weak  we
  weak    weak    we      ak   weak    weak    we  ak we
    weakweak      we      ak   wea       ak   we    akwe
      wea         we      ak   we        ak   we    akwe
      wea         we      ak   we        ak   we    akwe
      wea          eak  weak   we        ak    we  ak we
      wea            wea  ak   we        ak     weak  we
                                                      we
we      ak     wea  ak       weak                     we
 we    ak    wea  weak     wea  eak                   we
  we  ak    we      ak   wea      wea         we      we
   weak     we      ak   we        we         we      we
    we      we      ak   we        we         we      we
   we        wea  weak    wea    wea          weak  weak
weak           wea  akw      weak                weak


*/
using namespace std;
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <utility>
#include <bitset>
#include <set>
#include <string>
#include <stack>
#include <iomanip>
#include <map>
#include <memory.h>
#include <deque>

typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<LL>> vvl;

#define pb push_back
#define F first
#define S second
#define mid (LB+RB)/2
#define mkp make_pair

//iterators
#define iter(x) x.begin(),x.end()
#define aiter(a,n) a,a+n

//loops
#define REP(n) for (int ___=n;___--;)
#define REP0(i,n) for (int i=0;i<n;++i)
#define REP1(i,n) for (int i=1;i<=n;++i)
#define FOR(i,b,l,k) for (int i=b;i!=l;i+=k)
#define MEM(e,val) memset (e,val,sizeof(e))
#define FE(i,v) for (auto i:v)

/*
yungyao so weeeeeeeeeeeeeeeeeeeeeeeeeeak
8e7 so dian
FHVirus so dian
youou so dian
KYW so dian
hubert so dian
jass so dian
tingyu so dian
panda so dian
*/

//IO
#include <cstdio>
#include <iostream>
#include <fstream> //mainly for USACO, sometimes for benjidabiao
#define theyRSOOOOOOOOODIAN ios_base::sync_with_stdio(false),cin.tie(0);
//testing some stuff, still under construction
//a lot more useful while debug
inline void print(vector <int> v){
    for (auto i:v)
        cout << i << ' ';
    cout << '\n';
}
inline void print(vector <int> v,char sep,char end){
    for (auto i:v)
        cout << i << sep;
    cout << end;
}

//pbds
/*
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
using namespace __gnu_pbds;
*/

//constants
#include <climits>
const int maxn = 0,mod = 0;

//workspace

struct Node{
    LL x;
    bool left;
    LL preR,postL;
    int preRcnt,postLcnt;
    bool operator<(Node p){return x < p.x;}
    Node(int x,bool left):
        x(x),left(left),preR(left ? 0 : x),postL(left ? x : 0),preRcnt(!left),postLcnt(left){}
};

LL ans_base;
inline void solve1(){
    int n;
    cin >> n;
    vector <Node> v;

    REP(n){
        char a,b; int x,y;
        cin >> a >> x >> b >> y;
        ans_base += max(x,y) - min(x,y);

        if (a != b){
            ++ans_base;
            v.pb(Node(min(x,y),true));
            v.pb(Node(max(x,y),false));
        }
    }
    if (v.empty()) {cout << ans_base; return;}
    sort (iter(v));
    for (int i=1;i<v.size();++i){
        v[i].preR += v[i-1].preR;
        v[i].preRcnt += v[i-1].preRcnt;
    }
    for (int i=v.size()-1;i--;){
        v[i].postL += v[i+1].postL;
        v[i].postLcnt += v[i+1].postLcnt;
    }

    LL ans = LLONG_MAX;
    for (auto [x,t,pr,pl,prcnt,plcnt]:v){
        ans = min(ans,x * prcnt - pr + pl - x * plcnt);
    }
    cout << ans_base + ans * 2;
}

inline void solve2(){
}

signed main(){
    theyRSOOOOOOOOODIAN
    //for (int ;cin;)//use in multi-testcases and end in EOF problems
    //int t,i=1;for (cin >> t;i<=t;++i)//use in multi-testcases problems
    //cout << "Case #" << i << ": ",//use in Google, FB competitions
    int k;
    cin >> k;

    if (k == 1) solve1();
    else solve2();
    return 0;
}

Compilation message

bridge.cpp: In function 'void solve1()':
bridge.cpp:135:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     for (int i=1;i<v.size();++i){
      |                  ~^~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 456 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 456 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 47 ms 11392 KB Output is correct
13 Correct 62 ms 12456 KB Output is correct
14 Correct 46 ms 11788 KB Output is correct
15 Correct 35 ms 6496 KB Output is correct
16 Correct 49 ms 11976 KB Output is correct
17 Correct 47 ms 12364 KB Output is correct
18 Correct 53 ms 12124 KB Output is correct
19 Correct 61 ms 12444 KB Output is correct
20 Correct 53 ms 12032 KB Output is correct
21 Correct 57 ms 12344 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -