oj.uz

Submission #1092414

# Submission time Handle Problem Language Result Execution time Memory
1092414 2024-09-24T02:28:02 Z vjudge1 Pinball (JOI14_pinball) C++17
29 / 100
 369 ms 12380 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("popcnt")
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using lld = long double;
using ii = pair<int,int>;
using pll = pair<ll, ll>;
 
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<ii>;
using vpll = vector<pll>;
using vlld = vector<lld>;
 
// #define endl '\n'
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define gcd(a,b) __gcd(a,b)
#define sz(x) (int)x.size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fls cout.flush()
 
#define fore(i,l,r) for(auto i=l;i<r;i++)
#define fo(i,n) fore(i,0,n)
#define forex(i,r,l) for(auto i=r; i>=l;i--)
#define ffo(i,n) forex(i,n-1,0)
 
bool cmin(ll &a, ll b) { if(b<a){a=b;return 1;}return 0; }
bool cmax(ll &a, ll b) { if(b>a){a=b;return 1;}return 0; }
void valid(ll in) { cout<<((in)?"YES\n":"NO\n"); }
ll lcm(ll a, ll b) { return (a/gcd(a,b))*b; }
ll gauss(ll n) { return (n*(n+1))/2; }

const int N = 204;
ll dp[2][3*N][3*N];
/*
dp[i][c1][cn]
estando en la fila i cual es la minima suma de costos para que:
la ficha 1 este en la posicion rd[c1] y la ficha n este en la posicion rd[c2]
*/
struct device { ll a, b, c, d; };
void test_case() {
    ll n, m;
    cin >> n >> m;
    vector<device> a(n+1);
    deque<ll> rd;
    fore (i, 1, n+1) {
        cin >> a[i].a >> a[i].b >> a[i].c >> a[i].d;
        rd.pb(a[i].a);
        rd.pb(a[i].b);
        rd.pb(a[i].c);
    }
    rd.pb(1);
    rd.pb(m);
    sort(all(rd));
    fo(i, sz(rd)-1) if(rd[i+1] == rd[i]) rd[i] = 0;
    sort(all(rd));
    while(rd[0]==0) rd.pop_front();
    fo(i2, 3*n+2) fo(i3, 3*n+2) dp[0][i2][i3] = 1e18;
    dp[0][0][sz(rd)-1]=0;
    // for (int v: rd) cout << v << " ";
    // cout << '\n';
    // return;
    fore (i, 1, n+1) {
        // no hacer nada
        fo (i2, sz(rd)) fo(i3, sz(rd)) dp[i&1][i2][i3] = dp[i&1^1][i2][i3];
        // usar este y que se modifique al menos la posicion del 1
        int p = lower_bound(all(rd), a[i].c)-rd.begin();
        fo (i2, sz(rd)) {
            fo (i3, sz(rd)) { 
                int p2 = (a[i].a<=rd[i2] && rd[i2]<=a[i].b ? p : i2);
                int p3 = (a[i].a<=rd[i3] && rd[i3]<=a[i].b ? p : i3);
                dp[i&1][p2][p3] = min(dp[i&1][p2][p3], dp[i&1^1][i2][i3] + a[i].d);
            }
        }
    }
    ll ans = 1e18;
    fo (i, sz(rd)) ans=min(ans, dp[n&1][i][i]);
    if (ans == 1e18) cout << "-1\n";
    else cout << ans << '\n';
}

int main() {
    int tt = 1;
    // cin >> tt;
    while(tt--) test_case();
}

Compilation message

pinball.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("O3")
      | 
pinball.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("unroll-loops")
      | 
pinball.cpp: In function 'void test_case()':
pinball.cpp:75:62: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   75 |         fo (i2, sz(rd)) fo(i3, sz(rd)) dp[i&1][i2][i3] = dp[i&1^1][i2][i3];
      |                                                             ~^~
pinball.cpp:82:60: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   82 |                 dp[i&1][p2][p3] = min(dp[i&1][p2][p3], dp[i&1^1][i2][i3] + a[i].d);
      |                                                           ~^~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 8 ms 3704 KB Output is correct
10 Correct 50 ms 4188 KB Output is correct
11 Correct 88 ms 4444 KB Output is correct
12 Correct 369 ms 6196 KB Output is correct
13 Correct 368 ms 5980 KB Output is correct
14 Correct 355 ms 5980 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 8 ms 3704 KB Output is correct
10 Correct 50 ms 4188 KB Output is correct
11 Correct 88 ms 4444 KB Output is correct
12 Correct 369 ms 6196 KB Output is correct
13 Correct 368 ms 5980 KB Output is correct
14 Correct 355 ms 5980 KB Output is correct
15 Correct 5 ms 2136 KB Output is correct
16 Runtime error 11 ms 12380 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 8 ms 3704 KB Output is correct
10 Correct 50 ms 4188 KB Output is correct
11 Correct 88 ms 4444 KB Output is correct
12 Correct 369 ms 6196 KB Output is correct
13 Correct 368 ms 5980 KB Output is correct
14 Correct 355 ms 5980 KB Output is correct
15 Correct 5 ms 2136 KB Output is correct
16 Runtime error 11 ms 12380 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -