Submission #785646

#	Time	Username	Problem	Language	Result	Execution time	Memory
785646		canadavid1	Pyramid Base (IOI08_pyramid_base)	C++14	35 / 100	5060 ms	24236 KiB

pyramid_base

#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x),end(x)
#define rep(i,e) for(int i = 0; i < e; i++)
struct rect
{
    int sx,sy,ex,ey;
};
struct obstacle 
{
    rect p;
    int c;
};
vector<obstacle> ob;
int Xs,Ys,B,P;
bool intersects(rect a, rect b)
{
    // check intersection of each of the lines
    if(a.sx > b.ex || b.sx > a.ex) return false;
    if(a.sy > b.ey || b.sy > a.ey) return false;
    return true;
}
bool valid_position(rect pos)
{
    // for now just check every obstacle
    if (pos.ey > Ys || pos.ex > Xs) return false;
    int c = 0;
    for(auto &i : ob)
    {
        if(intersects(pos,i.p)) c += i.c;
        if(c > B) return false;
    }
    return true;
}
int main()
{
    cin >> Xs >> Ys >> B >> P;
    ob.resize(P);
    for(auto &&i : ob)
    {
        cin >> i.p.sx >> i.p.sy >> i.p.ex >> i.p.ey >> i.c;
    }
    vector<int> sx={1};
    for(auto &i : ob) sx.push_back(i.p.ex+1);
    vector<int> sy={1};
    for(auto &i : ob) sy.push_back(i.p.ey+1);
    int tops = 0;

    for(auto tsy : sy)
    {
        for(auto tsx : sx)
        {
            // binary search over sizes. but try tops first
            if(!valid_position({tsx,tsy,tsx+tops,tsy+tops})) continue;
            int l = tops;
            int r = min(Xs-tsx,Ys-tsy);
            while(r-l > 1)
            {
                int m = (r+l)/2;
                if(valid_position({tsx,tsy,tsx+m,tsy+m})) l = m;
                else r = m;
            }
            tops = l+1;
        }
    }
    cout << tops << "\n";
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 0 / 7
• Subtask 9: 0 / 7
• Subtask 10: 0 / 7
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 0 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10