답안 #508704

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
508704 2022-01-13T15:10:47 Z lukameladze NLO (COCI18_nlo) C++14
110 / 110
630 ms 328 KB
# 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() {
      | ^~~~
# 결과 실행 시간 메모리 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