oj.uz

Submission #785646

# Submission time Handle Problem Language Result Execution time Memory
785646 2023-07-17T11:13:56 Z canadavid1 Pyramid Base (IOI08_pyramid_base) C++14
35 / 100
 5000 ms 24236 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 324 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 212 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 340 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 45 ms 340 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 340 KB Output is correct
2 Correct 6 ms 356 KB Output is correct

Subtask #8
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 468 KB Output is correct
2 Correct 4796 ms 572 KB Output is correct
3 Execution timed out 5049 ms 468 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5056 ms 1108 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5019 ms 1460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5054 ms 1780 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5041 ms 2028 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5036 ms 12252 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5045 ms 19008 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5060 ms 24236 KB Time limit exceeded
2 Halted 0 ms 0 KB -