akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef unsigned long long ull;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int a[111111];
int b[111111];
const int MX = 211111;
const int INF = int(1e9);
struct edge
{
	int to,cap,rev;
	edge(int to=0,int cap=0,int rev=0):to(to),cap(cap),rev(rev){}
};
vector <edge> vec[MX];
int level[MX];
int iter[MX];

void addedge(int s,int t,int c) //adds an edge of cap c to the flow graph
{
	int S=vec[s].size(),T=vec[t].size();
	vec[s].push_back(edge(t,c,T));
	vec[t].push_back(edge(s,0,S));
}
void bfs(int s)
{
	memset(level,-1,sizeof(level));
	queue <int> que;
	level[s] = 0;
	que.push(s);
	while (!que.empty())
	{
		int v = que.front();que.pop();
		for(int i=0;i<vec[v].size();i++)
		{
			edge&e=vec[v][i];
			if (e.cap>0&&level[e.to]<0)
			{
				level[e.to]=level[v]+1;
				que.push(e.to);
			}
		}
	}
}
ll flow_dfs(int v,int t,ll f)
{
	if (v==t) return f;
	for(int &i=iter[v];i<vec[v].size();i++)
	{
		edge &e=vec[v][i];
		if (e.cap>0&&level[v]<level[e.to])
		{
			ll d=flow_dfs(e.to,t,min(f,ll(e.cap)));
			if (d>0)
			{
				e.cap-=d;
				vec[e.to][e.rev].cap+=d;
				return d;
			}
		}
	}
	return 0;
}
ll maxflow(int s,int t) //finds max flow using dinic from s to t
{
	ll flow = 0;
	while(1)
	{
		bfs(s);
		if (level[t]<0) return flow;
		memset(iter,0,sizeof(iter));
		while (1)
		{
			ll f=flow_dfs(s,t,INF);
			if(f==0) break;
			flow += f;
		}
	}
}

int ca[111111];
int cb[111111];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i]; 
	}
	for(int i=0;i<n;i++)
	{
		cin>>b[i]; 
	}
	memset(ca,-1,sizeof(ca));
	memset(cb,-1,sizeof(cb));
	int cc=0;
	for(int i=0;i<n;i++)
	{
		int c=i;
		if(ca[c]!=-1) continue;
		while(ca[c]==-1)
		{
			ca[c]=cc;
			c=a[c];
		}
		cc++;
	}
	cc=n;
	for(int i=0;i<n;i++)
	{
		int c=i;
		if(cb[c]!=-1) continue;
		while(cb[c]==-1)
		{
			cb[c]=cc;
			c=b[c];
		}
		cc++;
	}
	int s=MX-1; int e=MX-2;
	int res=n;
	for(int i=0;i<n;i++)
	{
		int l=ca[i]; int r=cb[i];
		if(a[i]==b[i])
		{
			if(a[i]==i)
			{
				res--; continue;
			}
			addedge(l,r,1);
			addedge(r,l,1);
		}
		else
		{
			if(a[i]!=i&&b[i]!=i)
			{
				addedge(r,l,1);
			}
			else if(a[i]==i)
			{
				addedge(r,e,1);
			}
			else
			{
				addedge(s,l,1);
			}
		}
	}
	cout<<res-maxflow(s,e)<<'\n';
}


Measured memory_bytes: 17024
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<queue>
using namespace std;
#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
typedef pair<int, int>P;
const int INF = 1e8;

signed main() {
	int N;
	cin >> N;
	int ans = (N + 2 - 1) / 2;
	cout << ans;
}

Measured memory_bytes: 256
n=int(input())
moji = []
for _ in range(n):
    s=input()
    moji.append(s)

mid_ab = 0
la_fb = 0
last_a = 0
first_b = 0

for s in moji:
    mojiretu=len(s)
    if s[0] == 'B' and s[-1] == 'A':
        la_fb += 1
    elif s[0] == 'B':
        first_b += 1
    elif s[-1] == 'A':
        last_a += 1
    for j in range(mojiretu-1):
        if s[j] == 'A' and s[j+1] == 'B':
            mid_ab += 1

if la_fb == 0:
    ans = mid_ab+min(last_a,first_b)
elif last_a == first_b == 0 and la_fb> 0:
    ans = mid_ab+la_fb-1
else:
    if la_fb <= abs(last_a-first_b):
        ans = mid_ab+min(last_a,first_b)+la_fb
    else:
        ans = mid_ab+max(last_a,first_b)+(la_fb-abs(last_a-first_b))
print(ans)

Measured memory_bytes: 45144
#include<bits/stdc++.h>
using namespace std;
int n;
long long int a[111111];
bool proc(){
	long long int s = 0;
	cin>>n;
	for(int i=0; i<n; i++){
		cin>>a[i];
		s += a[i];
	}
	long long int t = (1LL + n) * n / 2;
	if(s%t != 0)return false;
	s /= t;
	a[n] = a[0];
	long long int s2 = 0;
	for(int i=1; i<=n; i++){
		long long int w = -(a[i] - a[i-1] - s);
		if(w % n != 0 || w < 0)return false;
		s2 += w/n;
	}
	return s == s2;
}
int main(){
	cout << (proc()?"YES":"NO") <<endl;
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <set>
using namespace std;

int main(){
    int N;
    cin >> N;

    set<long long> onPaper;

    long long A;
    for(int i=0; i<N; i++){
        cin >> A;
        bool c = onPaper.erase(A);
        if(c==0){
            onPaper.insert(A);
        }
    }
    
    cout << onPaper.size() << endl;
    return 0;
}

Measured memory_bytes: 4864
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
MOD = 1000000007
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

L=II()
INL=LI()

ODDS=INL[::2]
EVNS=INL[1::2]

MP_ODDS = {}
MP_EVNS = {}

if L == 2:
    print(0)
    exit()

for i in ODDS:
    if not i in MP_ODDS:
        MP_ODDS[i] = 0
    MP_ODDS[i] += 1

for i in EVNS:
    if not i in MP_EVNS:
        MP_EVNS[i] = 0
    MP_EVNS[i] += 1

ODDSC = []
EVNSC = []
for i,j in MP_ODDS.items():
    ODDSC.append((j,i))
for i,j in MP_EVNS.items():
    EVNSC.append((j,i))
ODDSC.sort(reverse=True)
EVNSC.sort(reverse=True)
EVNSC.append((0, -1))
ODDSC.append((0, -1))

# print(ODDSC, L)
if ODDSC[0][1] == EVNSC[0][1]:
    print(min(L-ODDSC[1][0]-EVNSC[0][0], L-ODDSC[0][0]-EVNSC[1][0]))    
else:
    print(L - ODDSC[0][0] - EVNSC[0][0])


Measured memory_bytes: 64108
#include <algorithm>
#include<iostream>
#include<vector>
#include<deque>
#include<queue>
#include<list>
#include<stack>
#include<map>
#include<set>
#include<string>
#include <sstream>
#include<bitset>

#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<limits.h>

using namespace std;
const int INF = 0x7fffffff;

int gcd(int x,int y){
  int mi,ma;
  ma = max(x,y);
  mi = min(x,y);
  if(ma % mi == 0){
    return mi;
  }
  else{
    return gcd(mi,ma % mi);
  }
}

int main(){
  long ii,jj,kk;
  vector<int> a;
  int x;
  cin >> x;
  cout << x*x*x << endl;
  
  return 0;
}



Measured memory_bytes: 3084
#include <stdio.h>
#include <string.h>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define mp make_pair

int N, E, T, W[500], G[2000], C[2000], S[2000][16], dp[500];

int main() {
    scanf("%d%d%d", &N, &E, &T);
    T--;
    rep(i, N) scanf("%d", W+i);
    rep(i, E) {
        scanf("%d%d", G+i, C+i);
        G[i]--;
        rep(j, C[i]) scanf("%d", S[i]+j);
        rep(j, C[i]) S[i][j]--;
    }
    memset(dp, -1, sizeof(dp));
    priority_queue<pair<int, int> > q;
    rep(i, N) if(W[i]) q.push(mp(-1, i));
    while(!q.empty() && dp[T]==-1) {
        pair<int, int> vx(q.top());
        q.pop();
        const int ix = vx.second;
        if(dp[ix]!=-1) continue;
        dp[ix] = -vx.first;
        rep(i, E) if(dp[G[i]]==-1) {
            bool can = true;
            rep(j, C[i]) if(dp[S[i][j]]==-1) can = false;
            if(can) {
                vector<int> v;
                rep(j, C[i]) v.push_back(dp[S[i][j]]);
                sort(v.begin(), v.end(), greater<int>());
                int mx = 0;
                rep(j, v.size()) mx = max(mx, v[j]+j);
                q.push(mp(-mx, G[i]));
            }
        }
    }
    printf("%d\n", dp[T]);
    return 0;
}

Measured memory_bytes: 0
D, G = map(int, input().split())
P = []
C = []
for i in range(D):
    p, c = map(int, input().split())
    P.append(p)
    C.append(c)
ans = 100000000

for i in range(2 ** D):
    a = 0
    b = 0
    for j in range(D):
        if i >> j & 1:
            a += 100 * P[j] * (j + 1) + C[j]
            b += P[j]
    for k in range(D-1, -1, -1):
        if i >> k & 1:
            continue
        if a >= G:
            break
        for l in range(P[k]):
            a += 100 * (k + 1)
            b += 1
            if a >= G:
                break
    ans = min(ans, b)
print(ans)

Measured memory_bytes: 3064
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
using Graph=vector<vector<int>>;
template<class T> inline bool chmax(T &a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main(){
    int k,n;
    cin>>n>>k;
    vector<int> p(n);
    for(int i=0;i<n;++i) cin>>p[i];
    sort(p.begin(),p.end());

    int sum=0;
    for(int i=0;i<k;++i) sum+=p[i];
    cout<<sum<<endl;
}

Measured memory_bytes: 3612
#include <iostream>

using namespace std;

int main()
{

        int n = 0;
        cin >> n;
        int a = 0;
        if (n % 2) {
                a = n / 2;
        }
        else {
                a = n / 2 - 1;
        }
        cout << a << endl;

        return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 3e4 + 5;
const ll LINF = 1e18 + 5;
int n, nxt[N][10];
char s[N];
void build()
{
	for(int i=n;i>0;i--)
	{
		for(int j=0;j<10;j++) nxt[i-1][j] = nxt[i][j];
		nxt[i-1][s[i]-'0'] = i;
	}
}
int main()
{
 	ios::sync_with_stdio(false);
 	cin.tie(0);
 	cin >> n >> (s+1);
 	build();
 	int ans = 0;
 	for(int i=0;i<=9;i++)
 	{
 		int p = 0;
 		if(nxt[p][i])
 		{
 			for(int j=0;j<=9;j++)
 			{
 				int p1 = nxt[p][i];
 				if(nxt[p1][j])
 				{
 					for(int k=0;k<=9;k++)
 					{
 						int p2 = nxt[p1][j];
 						if(nxt[p2][k]) ans++;
 					}
 				}
 			}
 		}
 	}
 	cout << ans;	
	return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> pipii;
typedef pair<pii, int> piipi;
typedef pair<pii, pii> piipii;

#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define eb emplace_back

piipii c[405];
piipii rotate(piipii x){
    return mp(mp(x.se.se, x.fi.fi), mp(x.fi.se, x.se.fi));
}

ll get_idx(piipii x){
    return x.fi.fi*1ll*1000*1000*1000 + x.fi.se*1ll*1000*1000 + x.se.fi*1ll*1000 + x.se.se;
}
map<ll, int> dp;

void add(piipii p){
    for(int k=0;k<4;k++){
        dp[get_idx(p)]++;
        p = rotate(p);
    }   
}
void del(piipii p){
    for(int k=0;k<4;k++){
        dp[get_idx(p)]--;
        p = rotate(p);
    }
}

int main(){
    int n;
    scanf("%d", &n);   
    for(int i=1;i<=n;i++){
        scanf("%d%d%d%d", &c[i].fi.fi, &c[i].fi.se, &c[i].se.fi, &c[i].se.se);
        add(c[i]);
    }
    ll ans = 0;
    for(int i=1;i<=n;i++){
        piipii p1 = c[i];
        del(p1);
        for(int j=1;j<=n;j++){
            if(i == j) continue;
            piipii p2 = c[j];
            del(p2);
            for(int k=0;k<4;k++){
                ll res = 1;
                piipii tmp1 = mp(mp(p1.fi.se, p1.fi.fi), mp(p2.fi.se, p2.fi.fi));
                piipii tmp2 = mp(mp(p1.fi.se, p2.fi.fi), mp(p2.se.se, p1.se.fi));
                piipii tmp3 = mp(mp(p1.se.se, p1.se.fi), mp(p2.se.se, p2.se.fi));
                piipii tmp4 = mp(mp(p2.fi.se, p1.fi.fi), mp(p1.se.se, p2.se.fi));
                if(dp.find(get_idx(tmp1)) != dp.end()){
                    res *= dp[get_idx(tmp1)];
                    del(tmp1);
                }
                else res = 0;
                if(dp.find(get_idx(tmp2)) != dp.end()){
                    res *= dp[get_idx(tmp2)];
                    del(tmp2);
                }
                else res = 0;
                if(dp.find(get_idx(tmp3)) != dp.end()){
                    res *= dp[get_idx(tmp3)];
                    del(tmp3);
                }
                else res = 0;
                if(dp.find(get_idx(tmp4)) != dp.end()){
                    res *= dp[get_idx(tmp4)];
                    del(tmp4);
                }
                else res = 0;

                ans += res;

                if(dp.find(get_idx(tmp1)) != dp.end()){
                    add(tmp1);
                }
                if(dp.find(get_idx(tmp2)) != dp.end()){
                    add(tmp2);
                }
                if(dp.find(get_idx(tmp3)) != dp.end()){
                    add(tmp3);
                }
                if(dp.find(get_idx(tmp4)) != dp.end()){
                    add(tmp4);
                }

                p2 = rotate(p2);
            }
            add(p2);
        }
        add(p1);
    }
    printf("%lld\n", ans/6);
}

Measured memory_bytes: 3920
#include<bits/stdc++.h>
using namespace std;
int n,k,pri[1001];
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%d",&pri[i]);
	sort(pri+1,pri+1+n);
	long long ans=0;
	for(int i=1;i<=k;i++)
		ans+=pri[i];
	cout<<ans;
	return 0;
}

Measured memory_bytes: 3664
#include<bits/stdc++.h>
using namespace std;
main()
{
  int n;
  cin>>n;
  vector<long> v(n);
  for(int i=0;i<n;i++)cin>>v[i];
  long ans=v[0];
  for(int i=1;i<n;i++)
    ans=__gcd(ans,v[i]);
  cout<<ans<<"\n";
  
  
}

Measured memory_bytes: 1024
#include <iostream>
#include <math.h>
#include <string>
#include <algorithm>
#include <ctype.h>
#include <vector>
using namespace std;

#define ll long long int

int main()
{
    int a, b, x;

    cin >> a >> b >> x;
    if (a + b < x || a > x)
        cout << "NO" << endl;
    else
        cout << "YES" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define req(i,n) for(int i = 1;i <=n;i++)
#define pai 3.14159265358979323846
const int INF = 1001001001;
typedef long long ll;
int A[3][3], N;
bool punched[3][3];
bool ok[3][3];
using Graph = vector<vector<int>>;
vector<vector<int>> field;
vector<bool> seen;

const int MOD = 1000000007;
typedef pair<int,int> P;

//最大公約数
int gcd(int a,int b){
	if (a%b == 0){
		return b;
	}
	else{
		return gcd(b,a%b);
	}

}

//最小公倍数
int lcm(int a,int b){
	return a /gcd(a,b) * b;
}

//素数判定
bool is_prime(long long N) {
    if (N == 1) return false;
    for (long long i = 2; i * i <= N; ++i) {
        if (N % i == 0) return false;
    }
    return true;
}

// 素因数分解
vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

// 10進数から2進数
int binary(int bina){
    int ans = 0;
    for (int i = 0; bina>0 ; i++)
    {
        ans = ans+(bina%2)*pow(10,i);
        bina = bina/2;
    }
    return ans;
}







  


int main() {
 int k,x;
 cin >> k >> x;
 if (500*k >= x) cout << "Yes" << endl;
 else cout << "No" << endl;
}





Measured memory_bytes: 3692
#include<iostream>
using namespace std;
typedef long long ll;
int main() {
    int n; cin >> n;
    int table[5] = {0};
    for (int i = 0; i < n; ++i) {
        string s; cin >> s;
        if (s[0] == 'M') table[0]++;
        else if (s[0] == 'A') table[1]++;
        else if (s[0] == 'R') table[2]++;
        else if (s[0] == 'C') table[3]++;
        else if (s[0] == 'H') table[4]++;
    }
    ll ans = 0;
    for (int i = 0; i < (1 << 5); ++i) {
        int cnt = 0;
        ll tmp = 1;
        for (int j = 0; j < 5; ++j) {
            if (i & (1 << j)) {
                cnt++;
                tmp *= table[j];
            }
        }
        if (cnt == 3) {
            ans += tmp;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstring>

using namespace std;

// http://d.hatena.ne.jp/Nekonyan/20110508 
// Nekonyanツつウツづアツづ個コツーツドツづーツ参ツ考ツづ可つオツづ慊つオツつスツ。

int table[10+1][9999];
int memo[10];

void numnum (int size, int depth, int sum )
{
	if (size + 1 == depth ) {
		table[size][sum]++;
	}else{
		for (int i = 0; i <= 9; ++i ){
			if ( memo[i] == 0 ) {
				memo[i] = 1;
				numnum (size, depth + 1, sum + i*depth );
				memo[i] = 0;
			} // end if
		} // end for
	} // end if
}

int main()
{
	memset(table, 0, sizeof (table ) );

	for (int i = 1; i <= 10; ++i ) {
		memset (memo, 0, sizeof (memo ) );
		numnum (i, 1, 0 );
	} // end for

	int n, s;
	while ( cin >> n >> s ) {
		cout << table[n][s] << endl;
	} // end while

	return 0;
}

Measured memory_bytes: 1184
#include<bits/stdc++.h>
/*	#include <boost/math/common_factor.hpp>  boost::math::lcm(10,20) ---> use it to find lcm.*/
using namespace std;
#define IO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
//typedef long long ll;
#define int long long 
#define PI pair<int , int >
#define mpr make_pair
#define ff first
#define ss second
#define endl "\n"
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define FO(i,a,b) for(int i = (int)a;i < (int)b;++i)
#define FE(i,a,b) for(int i = (int)a;i <= (int)b;++i)
const int MOD = 1e9+7;
const int MAXN = 1e5+3;
const int inf = 2e9;
int max(int a,int b){	if(a > b)return a; else return b; }
int min(int a, int b){	if(a < b)return a; else return b; }
int dx[] = {1,-1,0,0};
int dy[] = {0,0,-1,1};
bool cmp(PI p1,PI p2){
	if(p1.ff < p2.ff)return true;	// You should not be writing p1.ss <= p2.ss !!!
	else if(p1.ff == p2.ff){ if(p1.ss < p2.ss)return true; return false; }
	return false;
}
/*		1. Take all the inputs
		4. Whenever you do multiplication and division in the same line, beware.
*/
void solve(){
	// int main  or  int32_t main ...
	int n,sum=0;
	cin >> n;
	for(int i=1;i<=n;i++){
		if(i%3!=0 && i%5!=0)sum += i;
	}
	cout << sum << endl;
}
/*	memset() can be used to set all values as 0 or -1 for integer data types.*/

int32_t main(){
	IO;
	#ifndef ONLINE_JUDGE
	//freopen("input.txt", "r", stdin);
	#endif // ONLINE_JUDGE
	// std::cout << std::setprecision(15); std::cout << std::fixed;
	int t; t = 1;
	// cin >> t;
	while(t--){ solve(); }
	return 0;
}


Measured memory_bytes: 3640
import java.util.*;

public class Main{
  static public void main(String[] args){
    
    Scanner sc = new Scanner(System.in);
    
    int N = sc.nextInt();
    int K = sc.nextInt();
    
    int[] sunuke = new int[N];
    for(int i=0; i<N; i++){
      sunuke[i] = 0;
    }
    
    int di, A;
    for(int j=0; j<K; j++){
      di = sc.nextInt();
      for(int k=0; k<di; k++){
        A = sc.nextInt();
        if(sunuke[A-1] == 0){
          sunuke[A-1]++;
        }
      }
    }
    
    int count = 0;
    for(int h=0; h<N; h++){
      if(sunuke[h] == 0){
        count++;
      }
    }
    
    System.out.println(count);
    
  }
}

Measured memory_bytes: 46308
def main():
    N = int(input())
    A = list(map(int, input().split()))

    c = [0] * (100000 + 1)
    for ai in A:
        c[ai] += 1

    ans = 0
    for i in range(len(c) - 2):
        ans = max(ans, c[i] + c[i+1] + c[i+2])
    print(ans)

if __name__ == "__main__":
    main()

Measured memory_bytes: 13964
import java.util.Scanner;

public class Main {

	public static void main(String[] args) 
	{
		Scanner sc = new Scanner(System.in);
		long n = sc.nextLong();
		long m = sc.nextLong();
		long d = sc.nextLong();
		
		double tester = 1;
		double cas = (n-d)*2;
		if(d==0)cas=n-d;
		cas*=(m-1);
		cas/=n;
		cas/=n;
		System.out.printf("%.12f", cas);
	}

}


Measured memory_bytes: 23764
/**
 * Created by yoshiwaratomohiro on 2017/06/18.
 */
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int N=scan.nextInt();
        int[] a=new int[N];
        int max=0;
        int min=N;

        for(int i=0;i<N;i++){
            a[i]=scan.nextInt();
            max=Math.max(a[i],max);
            min=Math.min(a[i],min);
        }
        if(max-min>1){
            System.out.println("No");
        }else if(max==min) {
            int maxcnt = 0;
            for (int i = 0; i < N; i++) {
                if (a[i] == max) {
                    maxcnt++;
                }
            }
            if(max*2<=maxcnt||max==maxcnt-1){
                System.out.println("Yes");
            }else{
                System.out.println("No");
            }
        }else {
                int mincnt=0;
                int maxcnt=0;
                for(int i=0;i<N;i++){
                    if(a[i]==max){
                        maxcnt++;
                    }else{
                        mincnt++;
                    }
                }
                max-=mincnt;
                if(max<1){
                    System.out.println("No");
                }else{
                    if(max*2>maxcnt){
                        System.out.println("No");
                    }else{
                        System.out.println("Yes");
                    }
                }
            }
        }
    }


Measured memory_bytes: 52132
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
using ll = long long int;
const ll INF = 1LL << 30;

ll N, M;

ll solve(vector<ll> cuts, vector< pair<ll, ll> > strands) {
    ll ret = 0;

    vector<ll> even, odd;
    even.push_back(0); odd.push_back(0);
    for(size_t i=1; i<cuts.size(); i++) {
        ll mo = i % 2, diff = cuts[i] - cuts[i-1];
        (mo ? odd : even).push_back( (mo ? odd : even).back() + diff );
        (mo ? even : odd).push_back( (mo ? even : odd).back()        ); // zero
    }

    for(auto e : strands) {
        ll l = e.first, r = e.second, sum = 0;
        sum += r - l;
        ll il = lower_bound(cuts.begin(), cuts.end(), l) - cuts.begin();
        ll ir = lower_bound(cuts.begin(), cuts.end(), r) - cuts.begin() - 1;

        if(ir - il >= 0) {
            if(il % 2 == 0) {
                sum -= odd [ir] - odd [il];
            }
            if(il % 2 == 1) {
                sum -= even[ir] - even[il];
            }

            if( (ir - il) % 2 == 0 ) {
                ll bound = cuts[ir];
                if(l < bound && bound < r) sum -= r - bound;
            }
        }

        // printf("[%lld, %lld], il = %lld, ir = %lld, len = %lld\n", l, r, il, ir, sum);
        ret += sum;
    }
    return ret;
}

int main() {
    scanf("%lld%lld", &N, &M);
    vector< pair<ll, ll> > strands, rev_strands;
    for(int i=0; i<N; i++) {
        ll l, r; scanf("%lld%lld", &l, &r);
        if(l < r) strands.push_back(make_pair(l, r));
        else rev_strands.push_back(make_pair(INF - l, INF - r));
    }

    vector<ll> cuts(M);
    for(int i=0; i<M; i++) {
        scanf("%lld", &cuts[i]);
    }

    ll ans = 0;
    sort(cuts.begin(), cuts.end());
    ans += solve(cuts, strands);
    reverse(cuts.begin(), cuts.end());
    for(auto &c : cuts) {
        c = INF - c;
    }
    ans += solve(cuts, rev_strands);
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 9184
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
const int maxn = 2e6 + 5;
const ll mod = 1e9 + 7;
const ll inf=0x3f3f3f3f;
const ld pi=acos(-1.0);
ll F[maxn],Finv[maxn],inv[maxn];//FÊÇ½×³Ë£¬FinvÊÇ½×³ËµÄÄæÔª

void init(){
    F[0]=Finv[0]=inv[1]=1;
    for(int i=2; i< maxn; i++)
        inv[i]=(mod-mod/i)*1ll*inv[mod%i]%mod;
    for(int i=1;i<maxn;i++){
        F[i]=F[i-1]*1ll*i%mod;
        Finv[i]=Finv[i-1]*1ll*inv[i]%mod;
    }
}
ll comb(int n, int m){
    if(m<0||m>n||n<0)return 0;
    return F[n]*1ll*Finv[n-m]%mod*Finv[m]%mod;
}
ll mypow(ll a, ll b){
    ll res=1;
    for(a%=mod;b;b>>=1,a=a*a%mod)
        if(b&1)res=res*a%mod;
    return res;
}
ll n,k;
string s;
void run(){
    cin>>k>>s;
    n=s.size();
    ll ans=0;
    for(int i=n;i<=k+n;i++){
        ll tmp=comb(i-1,n-1)*mypow(25,i-n)%mod*mypow(26,k+n-i)%mod;
        if(tmp<0)tmp+=mod;
        ans=(ans+tmp)%mod;
    }
    cout<<ans<<'\n';
}

int main(){
#ifdef haosao
freopen("main.h", "r", stdin);
#endif
    std::ios::sync_with_stdio(false);
    init();
    run();
    return 0;
}


Measured memory_bytes: 51112
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>

using namespace std;

int main() {
    int N, K;

    cin >> N >> K;

    vector<int> H;

    for(int i = 0; i < N; i++) {
        int h;
        cin >> h;
        H.push_back(h);
    }

    sort(H.begin(), H.end(), greater<int>());

    long long ans = 0;
    for(int i = K; i < H.size(); i++) {
        ans += H[i];
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1400
import itertools
def func(n):
  rest = {i ** 2 % n for i in range(1, n)}

  count = [0] * n
  for x, y in itertools.combinations(rest, 2):
    count[x - y] += 2

  for i in range(n // 2):
    print(count[i + 1] + count[n - i - 1])


def main():
  while True:
    n = int(input())
    if n == 0:
      break
    func(n)

main()


Measured memory_bytes: 6628
#include <iostream>
#include <cmath>

using namespace std;
using ll = long long;

int main()
{
    ll N, p{1};
    cin >> N;

    for (ll i = 1; i <= int(sqrt(N)); i++)
    {
        if (N / i * i == N)
        {
            p = i;
        }
    }
    cout << (p + N / p - 2) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
long N, A, B;
vector<long> S;
vector<long> dA, dB;
long memo[100001][3];
const long MOD = 1000000007;
bool checkA(int from, int to) {
  auto itr = lower_bound(dA.begin(), dA.end(), from + 1);
  if(itr == dA.end()) return true;
  return(*itr >= to);
}
bool checkB(int from, int to) {
  auto itr = lower_bound(dB.begin(), dB.end(), from + 1);
  if(itr == dB.end()) return true;
  return(*itr >= to);
}
long selectA(long idx);
long selectB(long idx);
long solve(long idx);
long selectA(long idx) {
  long ret = 0;
  //cout << "SelectA:" << idx << endl;
  if(memo[idx][1] >= 0) return memo[idx][1];
  long target = S[idx] + A;
  long last = -B * 2;
  long next = lower_bound(S.begin(), S.end(), target) - S.begin();
  //cout << "Next:" << next << endl;
  if(!checkB(idx + 1, next)) return memo[idx][1] = 0;
  if(next == N) {
    return memo[idx][1] = 1;
  }
  if(S[next] - S[next-1] >= B || next - 1 == idx){
    return memo[idx][1] = solve(next);
  }else{
    return memo[idx][1] = selectB(next - 1);
  }
  return memo[idx][1] = 1;
}
long selectB(long idx) {
  //cout << "SelectB:" << idx << endl;
  long ret = 0;
  if(memo[idx][2] >= 0) return memo[idx][2];
  long target = S[idx] + B;
  long last = -A * 2;
  long next = lower_bound(S.begin(), S.end(), target) - S.begin();
  //cout << "Next:" << next << endl;
  if(!checkA(idx + 1, next)) return memo[idx][2] = 0;
  if(next == N) {
    return memo[idx][2] = 1;
  }
  if(S[next] - S[next-1] >= A || next - 1 == idx){
    return memo[idx][2] = solve(next);
  }else{
    return memo[idx][2] = selectA(next - 1);
  }
}
long solve(long idx) {
  long ret = 0;
  //cout << "Sovle:" << idx << endl;
  // かならず選択の余地がある状態
  // Aを選択
  if(idx == N) return 1;
  if(memo[idx][0] >= 0) return memo[idx][0];
  ret = selectA(idx) + selectB(idx);
  if(ret >= MOD) ret -= MOD;
  return memo[idx][0] = ret;
}
int main() {
  cin >> N >> A >> B;
  S = vector<long>(N);
  for(int i = 0; i < N; i++) {
    cin >> S[i];
  }
  for(int i = 1; i < N; i++) {
    if(S[i] - S[i-1] < A) dA.push_back(i);
    if(S[i] - S[i-1] < B) dB.push_back(i);
  }
  memset(memo, -1, sizeof(memo));
  cout << solve(0) << endl;
}

Measured memory_bytes: 10484
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;
int main(){
    int n,m;
    cin >>n>>m;
    vector<int> s(m),c(m);
    rep(i,m)cin >>s[i]>>c[i];
    int ans =1000000007;
    int ansf =0;
    for( int i=0;i<1000;i++){
        bool flag =true;
        int cnt =0;
        int a=i;
        while(a>=10){
          a/=10;
          cnt++;
        }
        if (cnt!=n-1) {
          flag=false;
        }
        string str =to_string(i);
        if (flag){
          rep(j,m){
            string strc = to_string(c[j]);
            if (str.substr(s[j]-1,1)!=strc) flag= false;
          }
        }
        SKIP:
        if (flag){
            ans = min (ans,i);
            ansf++;
        }
    }
  if (m==0 &&n==1) {
    ansf++;
    ans =0;
  }else if (m==0 &&n!=1){
    ansf++;
    ans =pow(10,n-1);
  }
  if (ansf){
    cout << ans;
  }else{
    cout <<"-1";
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int NMAX = 2e5 + 10;
const int MOD = 1e9 + 7;
const double PI = acos(-1);


int main(int argc, char const *argv[])
{
	int a,b,h,m;
	scanf("%d%d%d%d",&a,&b,&h,&m);
	double theta = 1.0*m/30*PI - (1.0*h/6*PI + 1.0*m/360*PI);
	printf("%.11lf\n", sqrt(a*a + b*b -2*a*b*cos(theta)));
	return 0;
}

Measured memory_bytes: 4256
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
 
using namespace std;
 
const double eps = 1e-9;
 
 
bool eq(double a, double b){
  return abs(b-a)<eps;
}
 
bool ls(double a, double b){
  return !eq(a,b) && a<b;
}
 
class Point{
public:
  double r,x,y;
  bool operator<(const Point &a)const{
    if(!eq(x,a.x))return ls(x,a.x);
    return ls(y,a.y);
  }
   
  double dist(const Point &a)const{
    return sqrt((a.x-x)*(a.x-x)+(a.y-y)*(a.y-y))-r-a.r;
  }
};
 
double min_val = 1e80;
const double MAXPOINT = 1e80;
 
Point BigPoint = {0,MAXPOINT,MAXPOINT};
 
void Merge(Point *a, int l, int mid, int r, double midx){
  int n1 = mid-l+1, n2 = r-mid,pr=0,pl=0;
  Point L[n1+1], R[n2+1];
  for(int i = 0; i < n1; ++i) L[i] = a[l+i];
  for(int i = 0; i < n2; ++i) R[i] = a[mid+1+i];
   
  L[n1] = R[n2] = BigPoint;
  for(int i = l; i < r + 1; ++i){
    if( L[pl].y < R[pr].y ) a[i] = L[pl++];
    else a[i] = R[pr++];
  }
  Point p1 = BigPoint, p2 = BigPoint, p3 = BigPoint, p4 = BigPoint;
  for(int i = l; i < r+1; ++i){
    //if( ls( abs(midx-a[i].x), min_val) ){
      min_val = min(min_val, a[i].dist(p1));
      min_val = min(min_val, a[i].dist(p2));
      min_val = min(min_val, a[i].dist(p3));
      min_val = min(min_val, a[i].dist(p4));
      p1=p2;p2=p3;p3=p4;p4=a[i];
      //}
  }
}
 
void MergeSort( Point *a, int l, int r){
  if(l<r){
    int q = (r+l)/2;
    double midx = a[q].x;
    MergeSort(a,l,q);
    MergeSort(a,q+1,r);
    Merge(a,l,q,r,midx);
  }
}
 
int main()
{
  int n;
  while(cin >> n && n){
    Point a[n];
    min_val = 1e80;
    for(int i = 0; i < n; ++i)cin>>a[i].r>>a[i].x>>a[i].y;
    sort(a,a+n);
    MergeSort(a,0,n-1);
    cout << fixed << setprecision(10) << min_val << endl;
  }
  return 0;
}

Measured memory_bytes: 5692
/**
 *    author:  otera    
**/
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<deque>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

#define int long long
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
const int inf=1e9+7;
const ll INF=1LL<<60 ;
const ll mod=1e9+7 ;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<int, int> P;
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
#define debug(x)  cerr << #x << " = " << (x) << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int memo[220][220];

int gcd(int a, int b) {
    if(memo[a][b] != -1) return memo[a][b];
    if(b == 0) return a;
    return memo[a][b] = gcd(b, a % b);
}

void solve() {
	int k; cin >> k;
    int ans = 0;
    rep(i, 220) {
        rep(j, 220) {
            memo[i][j] = -1;
        }
    }
    for(int a = 1; a <= k; ++ a) {
        for(int b = 1; b <= k; ++ b) {
            for(int c = 1; c <= k; ++ c) {
                int d = gcd(a, b);
                int e = gcd(d, c);
                ans += e;
            }
        }
    }
    cout << ans << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//int t; cin >> t; rep(i, t)solve();
	solve();
    return 0;
}

Measured memory_bytes: 4028
#include <bits/stdc++.h>
using namespace std;

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

    int a,b,c,x,y;
    cin>>a>>b>>c>>x>>y;

    int ans=0;

    if(a+b>c+c)ans+=min(x,y)*(c+c);
    else ans+=min(x,y)*(a+b);

    if(a<c+c)ans+=max(0,x-y)*a;
    else ans+=max(0,x-y)*(c+c);

    if(b<c+c)ans+=max(0,y-x)*b;
    else ans+=max(0,y-x)*(c+c);

    cout<<ans<<"\n";

    return 0;
}


Measured memory_bytes: 3648
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    a = int(input())
    b = int(input())
    for i in range(1, 4):
        if i==a or i==b:
            continue
        print(i)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3316
#include<bits/stdc++.h>

#define rep(i,N) for(int i=0;i<N;i++)
#define rep2(i,N) for(int i=1;i<=N;i++)
using namespace std;
long long  INF=1e18;
long long mod=1e9+7;

typedef pair<long long,long long>P;
int v,e,r;

vector<P>edge[100010];



//practicing
vector<long long>dijkstra(int start){

    vector<long long>dist(v,INF);
    dist[start]=0;

    priority_queue<P,vector<P>,greater<P>>pq;

    pq.push(P(dist[start],start));

    while(!pq.empty()){

    auto now=pq.top();
    pq.pop();
    
    long long d=now.first;
    int from=now.second;
    if(dist[from]<d)continue;

        for(auto nxt:edge[from]){
            int to=nxt.first;
            long long c=nxt.second;

            if(dist[from]+c<dist[to]){
                dist[to]=dist[from]+c;
                pq.push(P(dist[to],to));
            }
        }

    }

    return dist;
}
int main(){
    
    cin>>v>>e>>r;

    for(int i=0;i<e;i++){
        int s,t;
        long long d;
        cin>>s>>t>>d;
        edge[s].push_back(P(t,d));
    }
    auto dist=dijkstra(r);

    for(int i=0;i<v;i++){
        if(dist[i]==INF)cout<<"INF"<<endl;
        else{
            cout<<dist[i]<<endl;
        }
    }

    return 0;

}
/*


*/



Measured memory_bytes: 19392
#include<bits/stdc++.h>
using namespace std;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
//  long long int n,k,ans=1;
 long long int n;
 cin>>n;
 if(n==1)
    cout<<"Yes";
 else{
 int j=0;
 for(int i=2;i<10;i++)
 {

     if(n%i==0)
     {
         int t=n/i;
         if(t<10)
            {j=1;
            break;
            }
     }
 }
 if(j==0)
cout<<"No";
else
    cout<<"Yes";
  }
}


Measured memory_bytes: 3644
#include<stdio.h>
#include<string.h>
#define N 100
void bubbleSort(int [],int);
void printArray(int [],int);
int count;
int main(){
  int n,A[N],i;
  count = 0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  bubbleSort(A,n);
  printArray(A,n);
  return 0;
}
void bubbleSort(int A[],int n){
  int i,j;
  for(i=0;i<n;i++){
    for(j=n-1;j>i;j--){
      if( A[j-1] > A[j] ){
	int tmp = A[j-1];
	A[j-1] = A[j];
	A[j] = tmp;
	count++;
      }
    }
  }
  return ;
}
void printArray(int A[],int n){
  int i;
  for(i=0;i<n;i++){
    if( i!=0 ){
      printf(" ");
    }
    printf("%d",A[i]);
  }
  printf("\n%d\n",count);
} 

Measured memory_bytes: 604
#include<iostream>
#include<vector>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
using namespace std;
int main(){
  int a,b;
  while(cin>>a>>b,a||b){
    vector<int>in(a);
    rep(i,a)cin>>in[i];
    int sum=0;
    rep(i,b)sum+=in[i];
    int ma=sum;
    rep(i,a-b){
      sum-=in[i];
      sum+=in[i+b];
      ma=max(ma,sum);
    }
    cout<<ma<<endl;
  }

}

Measured memory_bytes: 1532
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Program
{
    static void Main(string[] args)
    {
        double[] arr = Console.ReadLine().Split(' ').Select(v => double.Parse(v)).ToArray();
        double a = arr[0];
        double b = arr[1];
        b = b * 100 + 0.5;
        long al = (long)a;
        long bl = (long)b;
        long ansl = al * bl;
        ansl /= 100;
        Console.WriteLine(ansl);
    }

   

}




Measured memory_bytes: 18864
#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) ((x < 0)?-(x):x)
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

typedef long long cat;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	string S;
	cin >> S;
	vector<int> P(26), used(26, 0);
	for(int i = 0; i < (int)S.length(); i++) {
		P[i] = S[i]-'a';
		used[P[i]] = 1;
	}
	int a = 0;
	for(int i = S.length(); i < 26; i++) {
		while(used[a]) a++;
		P[i] = a;
		used[a] = 1;
	}

	if((int)S.length() < 26) {
		for(int i = 0; i <= (int)S.length(); i++) cout << (char)('a'+P[i]);
		cout << "\n";
		return 0;
	}
	vector<int> P0 = P;
	if(!next_permutation(begin(P), end(P))) {
		cout << "-1\n";
		return 0;
	}
	for(int i = 0; i < 26; i++) if(P0[i] != P[i]) {
		for(int j = 0; j <= i; j++) cout << (char)('a'+P[j]);
		cout << "\n";
		return 0;
	}
	return 0;}

// look at my code
// my code is amazing


Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef long long int64;
typedef pair<int,int> pii;
typedef vector<int> vi;

const double eps = 1e-9;
const int oo = 0x3f3f3f3f;
const int mod = 1000000007;

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

    int h, w, a, b;
    cin >> h >> w >> a >> b;

    for (int i = 0; i < h; ++i){
        for (int j = 0; j < w; ++j){
            cout << ((j < a) ^ (i < b));
        }
        cout << endl;
    }

    return 0;
}

Measured memory_bytes: 1280
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cassert>
#include <vector>
#include <string>
#include <cmath>
#include <map> 
#include <sstream>
#include <cstdio>
#include <complex>
#include <cstring>
using namespace std;
 
const int MAX= 10000100;

#define loop(i,a,b) for(int i = a ; i < b ; i ++)
#define rep(i,a) loop(i,0,a)
#define all(a) (a).begin(),(a).end()
#define ll long long int
#define gcd(a,b) __gcd(a,b)
#define pb(a) push_back(a)
int GCD(int a, int b) {if(!b) return a; return gcd(b, a%b);}
int lcm(int a, int b) {return a*b / gcd(a, b);}

char maze[110][110];
int dx[] = {0,1,0,-1} , dy[] = {-1,0,1,0};
int size;

bool over(int x,int y){
  return x < 0 || size <= x || y < 0 || size <= y;
}
bool space(int x,int y){
  int cnt = 0;
  rep(i,4){
    int nx = x + dx[i], ny = y + dy[i];
    if(maze[ny][nx] == '#')
      cnt ++;
  }
  return cnt > 1;
}
void dfs(int x,int y,int d){
  if(size <= x) 
    dfs(x-1,y,2);
  if(y < 0)
    dfs(x,y+1,1);
  if(size <= y)
    dfs(x,y-1,3);
  if(space(x,y))
    return ;
  if(over(x,y))return;
  maze[y][x] = '#';
  
  int nnx = x + 2 * dx[d] , nny = y + 2 * dy[d];
  if(maze[nny][nnx] == '#')
    d = (d+1)%4;
  dfs(x+dx[d],y+dy[d],d);

}

void solve(int n){
  size = n;
  dfs(0,n-1,0);
  rep(i,n){
    rep(j,n){
      cout<<maze[i][j];
    }
    cout<<endl;
  }
}

int main(void){
  int n,in;
  cin>>n;
  rep(time,n){
    cin>>in;
    if(time)cout<<endl;

    rep(i,in)rep(j,in)maze[i][j] = ' ';
    solve(in);
   
  }
}

Measured memory_bytes: 1164
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (ll i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define pb push_back
using ll = long long;
using ld=long double;
using vin=vector<int>;
using vvin=vector<vin>;
using vll=vector<ll>;
using vvll=vector<vll>;
using vst=vector<string>;
using P = pair<ll,ll>;
const int inf=1e9+7;
const ll INF=9e18;
template <typename T> bool chmin(T &a, const T& b){if(a > b){a = b;return true;}return false;}
template <typename T> bool chmax(T &a, const T& b){if(a < b){a = b;return true;}return false;}
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };

int main(){cout<<fixed<<setprecision(20);
		   int x;
           cin>>x;
           cout<<(!x)<<endl;
}

Measured memory_bytes: 3600
#ABC122C 累積和
from itertools import accumulate
A = []
N, Q = map(int, input().split())
B = [0]*N
S = list(input())
ans = []
for i in range(1, N):
    if S[i-1]=='A' and S[i]=='C':
        B[i] = 1
A = list(accumulate(B))
for j in range(Q):
    l, r = map(int, input().split())
    ans.append(A[r-1]-A[l-1])
print('\n'.join(map(str, ans)))

Measured memory_bytes: 19520
#include"bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using pi = pair<int, int>;
const ll INF = 1LL << 60;

int main() {
	int k, s,sum=0;
	cin >> k >> s;
	int z=0,cnt=0;
	for (int x = k; x >= 0; x--) {
		for (int y = k; y >= 0; y--) {
			z = s - (x + y);
			sum = x + y + z;
			if (0 <= z &&z <= k && sum == s)cnt++;
		}
	}
	cout << cnt << endl;
	return 0;
}



Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100, mod = 1000000007, inf = 0x3f3f3f3f;
int n, h[maxn + 10], ans;
int f[maxn + 10][maxn + 10][2][2][2], tmp[2][2][2];
int add(int x, int y) {
	x += y; return x < mod ? x : x - mod;
}
int dec(int x, int y) {
	x -= y; return x < 0 ? x + mod : x;
}
int mul(int x, int y) {
	return 1ll * x * y % mod;
}
int fpow(int x, int y) {
	int ans = 1;
	while (y) {
		if (y & 1) ans = mul(ans, x);
		y >>= 1; x = mul(x, x);
	}
	return ans;
}

int calcmin(int l, int r) {
	int ans = inf;
	for (int i = l; i <= r; ++i) ans = min(ans, h[i]);
	return ans;
}

void upd(int l, int r, int h) {
	for (int i = 0; i < 2; ++i)
		for (int j = 0; j < 2; ++j)
			for (int k = 0; k < 2; ++k)
				tmp[i][j][k] = 0;
	for (int i = 0; i < 2; ++i)
		for (int j = 0; j < 2; ++j) {
			if (h) {
				tmp[i][j][0] = add(tmp[i][j][0], mul(f[l][r][i][j][0], fpow(2, h - 1)));
				tmp[j][i][0] = add(tmp[j][i][0], mul(f[l][r][i][j][0], fpow(2, h - 1)));
			} else tmp[i][j][0] = add(tmp[i][j][0], f[l][r][i][j][0]);
			if (h & 1) tmp[i ^ 1][j ^ 1][1] = add(tmp[i ^ 1][j ^ 1][1], f[l][r][i][j][1]);
			else tmp[i][j][1] = add(tmp[i][j][1], f[l][r][i][j][1]);
		}
	for (int i = 0; i < 2; ++i)
		for (int j = 0; j < 2; ++j)
			for (int k = 0; k < 2; ++k)
				f[l][r][i][j][k] = tmp[i][j][k];
}

void merge(int l, int r, int ll, int rr) {
	for (int i = 0; i < 2; ++i)
		for (int j = 0; j < 2; ++j)
			for (int k = 0; k < 2; ++k)
				tmp[i][j][k] = 0;
	for (int i = 0; i < 2; ++i)
		for (int j = 0; j < 2; ++j)
			for (int k = 0; k < 2; ++k)
				for (int s = 0; s < 2; ++s)
					for (int p = 0; p < 2; ++p)
						for (int q = 0; q < 2; ++q) {
							int st = i, ed = p, t = k || q || (j == s);
							tmp[st][ed][t] = add(tmp[st][ed][t], mul(f[l][r][i][j][k], f[ll][rr][s][p][q]));
						}
	for (int i = 0; i < 2; ++i)
		for (int j = 0; j < 2; ++j)
			for (int k = 0; k < 2; ++k)
				f[l][r][i][j][k] = tmp[i][j][k];
}

void dp(int l, int r) {
	if (l == r) {
		f[l][r][0][0][0] = f[l][r][1][1][0] = 1;
	} else {
		int minv = calcmin(l, r);
		int lst = l - 1;
		vector<pair<int, int> > vec;
		for (int i = l; i <= r; ++i)
			if (h[i] == minv) {
				if (lst + 1 <= i - 1) vec.push_back(make_pair(lst + 1, i - 1));
				vec.push_back(make_pair(i, i)); lst = i;
			}
		if (lst < r) vec.push_back(make_pair(lst + 1, r));
		for (int i = 0; i < vec.size(); ++i) {
			pair<int, int> e = vec[i];
			dp(e.first, e.second);
			upd(e.first, e.second, calcmin(e.first, e.second) - minv);
			if (i) merge(l, r, e.first, e.second);
			else {
				for (int j = 0; j < 2; ++j)
					for (int k = 0; k < 2; ++k)
						for (int s = 0; s < 2; ++s)
							f[l][r][j][k][s] = f[e.first][e.second][j][k][s];
			}
		}
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d", &h[i]);
	dp(1, n);
	upd(1, n, calcmin(1, n) - 1);
	for (int i = 0; i < 2; ++i)
		for (int j = 0; j < 2; ++j)
			for (int k = 0; k < 2; ++k)
				ans = add(ans, f[1][n][i][j][k]);
	printf("%d", ans);
}

Measured memory_bytes: 640
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
R,C,K=map(int, sys.stdin.readline().split())

value=defaultdict(lambda: 0)
value=[ [0 for _ in range(C+1)] for __ in range(R+1) ]
for _ in range(K):
    r,c,v=map(int, sys.stdin.readline().split())
    value[r][c]=v

dp0=[0]*(C+1)
dp1=[0]*(C+1)
dp2=[0]*(C+1)
dp3=[0]*(C+1)

for r in range(1,R+1):
    for c in range(1,C+1):
        #今のマスにアイテムがある場合
        if 0<value[r][c]:
            dp3[c]=max( dp3[c-1], dp2[c-1]+value[r][c] )
            dp2[c]=max( dp2[c-1], dp1[c-1]+value[r][c] )
            dp1[c]=max( dp1[c-1], dp0[c-1]+value[r][c], dp0[c]+value[r][c] )
            dp0[c]=max( dp0[c-1], dp0[c] )
        #今のマスにアイテムがない場合
        else:
            dp0[c]=max( dp0[c-1], dp0[c] )
            dp1[c]=max( dp1[c-1], dp1[c] )
            dp2[c]=max( dp2[c-1], dp2[c] )
            dp3[c]=max( dp3[c-1], dp3[c] )

    #上の行にアイテムをコピー
    for c in range(1,C+1):
        dp0[c]=max( dp0[c], dp1[c], dp2[c], dp3[c] )
    dp1=[0]*(C+1)
    dp2=[0]*(C+1)
    dp3=[0]*(C+1)

print dp0[C]


Measured memory_bytes: 152940
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int INF=1e9;

int main(){
    int n,m;
    cin>>n>>m;
    int a[m],b[m],c[m],dp[n][n];
    fill(dp[0],dp[n],INF);
    for(int i=0;i<n;i++)dp[i][i]=0;
    for(int i=0;i<m;i++){
        cin>>a[i]>>b[i]>>c[i];
        a[i]--,b[i]--;
        dp[a[i]][b[i]]=dp[b[i]][a[i]]=c[i];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int k=0;k<n;k++){
                dp[j][k]=min(dp[j][k],dp[j][i]+dp[i][k]);
            }
        }
    }
    int ans=0;
    for(int i=0;i<m;i++){
        if(dp[a[i]][b[i]]!=c[i])ans++;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    n0 = 0
    n4 = 0
    for i in a:
        if i%2 == 1:
            n0 += 1
        if i%4 == 0:
            n4 += 1
    if n0+n4 == n and n0 == n4+1:
        print("Yes")
    elif n0 > n4:
        print("No")
    else:
        print("Yes")

    return

if __name__ == '__main__':
    main()


Measured memory_bytes: 59628