제출 #1177645

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1177645		vnedu	Pinball (JOI14_pinball)	C++20	11 / 100	8 ms	328 KiB

pinball

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }

#define fi first
#define se second

#define pb push_back
#define ii pair<int, int>

#define all(x) x.begin(), x.end()

#define TASK "nonsense"

/// end of template ///

const int ROW = 1e5 + 15;
const int COL = 1e9 + 19;
int numRow,numCol;
struct node
{
    int l,x,r,c;
    node() {}
    void input()
    {
        cin>>l>>r>>x>>c;
    }
} a[ROW];
namespace sub1
{
    bool check()
    {
        return (numRow<=10 && numCol<=1000);
    }
    void solve()
    {
        ll ans=LLONG_MAX;
        for (int mask=0; mask<(1<<numRow); ++mask)
        {
            bool ok=1;
            int lst=-1;
            for (int tri=1; tri<=numCol; ++tri)
            {
                int pos=tri;
                for (int k=2; k<=numRow+1; ++k)
                {
                    if (((mask>>(k-2))&1) && a[k-1].l<=pos && pos<=a[k-1].r) pos=a[k-1].x;
                }
                if (tri==1) lst=pos;
                else if (lst!=pos)
                {
                    ok=0;
                    break;
                }
            }
            if (ok)
            {
                ll sum=0;
                for (int j=0; j<numRow; ++j) if ((mask>>j)&1) sum+=a[j+1].c;
                minimize(ans,sum);
            }
        }
        cout<<(ans==LLONG_MAX?-1:ans);
    }
}
void solve()
{
    cin>>numRow>>numCol;
    for (int i=1; i<=numRow; ++i) a[i].input();
    if (sub1::check()) return void(sub1::solve());
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);

    int testcase=1;
//    cin>>testcase;

    while (testcase--)
        solve();

//    #define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
//    cerr << "Time elapsed: " << TIME << " s.\n";
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 49