Submission #508704

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
508704	2022-01-13T15:10:47 Z	lukameladze	NLO (COCI18_nlo)	C++14	110 / 110	630 ms	328 KB

nlo

# include <bits/stdc++.h>
#define f first
#define int long long
#define s second
#define pb push_back
#define pii pair <int, int>
using namespace std;
const int N = 105;
int t,n,k,x[N],y[N],r[N],sum,kat,ans,rem,mx,sz,m,ans1;
multiset <int> ms;
vector < pii > v;
char ch;
main() {
	std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	cin>>k;
	for (int i = 1; i <= k; i++) {
	    cin>>x[i]>>y[i]>>r[i];
	}
	for (int i = 1; i <= n; i++) {
	    v.clear(); ms.clear();
	    for (int j = k; j >= 1; j--) {
	        if (abs(x[j] - i) > r[j]) continue;
	        kat = abs(x[j] - i);
	        rem = (r[j]*r[j])-(kat*kat);
	        rem = sqrtl(rem);
	        //cout<<y[j]-rem<<" "<<y[j] + rem<<" " <<j<<endl;
	        v.pb({y[j] - rem, j});
	        v.pb({y[j] + rem + 1, -j});
	    }
	    ans1 = m * k;
	    v.pb({m+1,0});sort(v.begin(),v.end());
	    for (int j = 0; j < (int)v.size() - 1; j++) {
	        if (v[j].s >= 0) {
	            ms.insert(v[j].s);
	        } else {
	            //cout<<ms.count(-v[j].s)<<"S"<<endl;
	            ms.erase(ms.find(-v[j].s));
	        }
	        if (ms.size()) {
    	        mx = *(--ms.end());
    	        rem = mx;
    	        if (v[j + 1].f >= v[j].f) {
        	        sz = (v[j + 1].f - v[j].f);
        	        ans1 -= rem * sz;
        	       // cout<<i<<" "<<rem<<" "<<v[j].f<<" "<<v[j + 1].f<<endl;
    	        }
	        }
	    }
	    ans += ans1;
	}
	cout<<ans<<endl;
}

Compilation message

nlo.cpp:13:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   13 | main() {
      | ^~~~

Subtask #1

110.0 / 110.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	204 KB	Output is correct
2	Correct	9 ms	328 KB	Output is correct
3	Correct	5 ms	204 KB	Output is correct
4	Correct	48 ms	320 KB	Output is correct
5	Correct	28 ms	204 KB	Output is correct
6	Correct	250 ms	308 KB	Output is correct
7	Correct	80 ms	300 KB	Output is correct
8	Correct	459 ms	308 KB	Output is correct
9	Correct	138 ms	204 KB	Output is correct
10	Correct	630 ms	312 KB	Output is correct