akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define loop(i,a,b) for(int i=a;i<b;i++)
#define test() int t;cin>>t;loop(test,1,t+1)
#define pb push_back
#define eb emplace_back
#define mkp make_pair
#define nl cout<<"\n"
#define sp cout<<" "
#define F first
#define S second
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<pii>
#define vll vector<pll>
#define MOD 1000000007
#define all(x) x.begin(),x.end()

template<class C> void min_self( C &a, C b ){ a = min(a,b); }
template<class C> void max_self( C &a, C b ){ a = max(a,b); }

void mod( ll &n, ll m=MOD ){ n%=m,n+=m,n%=m; }

const int MAXN = 2005;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

int row[MAXN][MAXN]={};
int col[MAXN][MAXN]={};

int main() 
{
    fastio();

    int n,m;
    cin>>n>>m;
    vector<string>a(n);
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        for(int j=0;j<m;j++)
        {
            if( i && a[i][j] == '.' )
                col[i][j] = col[i-1][j] + 1;
            else
                col[i][j] = (a[i][j]=='.');

            if( j && a[i][j] == '.' )
                row[i][j] = row[i][j-1] + 1;
            else
                row[i][j] = (a[i][j]=='.');
        }
    }

    for(int i=0;i<n;i++)
    {
        for(int j=m-2;j>=0;j--)
        {
            if( row[i][j] && row[i][j+1] )
            {
                row[i][j] = row[i][j+1];
            }
        }
    }


    for(int j=0;j<m;j++)
    {
        for(int i=n-2;i>=0;i--)
        {
            if( col[i][j] && col[i+1][j] )
            {
                col[i][j] = col[i+1][j];
            }
        }
    }

    int mx = 0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            int r = row[i][j];
            int c = col[i][j];
            mx = max(mx, r+c-1);
        }
    }

    cout<<mx;


    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}

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

int main() {
  int n;
  cin >> n;
  vector<long long> a(n);

  for (int i = 0; i < n; i++) {
      cin >> a[i];
  }

  vector<long long> b(n+1);
  b[0] = 0;

  for (int i = 1; i < n+1; i++) {
      b[i] = b[i-1]+a[i-1];
  }

  map<long long, long long> nums;
  for (int i = 0; i < n+1; i++) {
      nums[b[i]]++;
  }

  long long res = 0;
  for (auto it : nums) {
      long long num = it.second;
      res += num * (num - 1) / 2;
  }

  cout << res << endl;

}


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

int GetLowerApproximatedArea(int Delta)
{
	int SumArea = 0;
	for(int i = 0; Delta * i < 600; i++){
		SumArea += Delta * Delta * i * Delta * i;
	}
	return SumArea;
}

int main()
{
	while(true){
		int Delta;
		cin >> Delta;
		if(cin.eof() == true) break;
		cout << GetLowerApproximatedArea(Delta) << endl;
	}
	return 0;
}

Measured memory_bytes: 3088
import sys

K, S = map(int, input().split())

ans = 0
if S == (3 * K):
    ans = 1
    print(ans)
    sys.exit()

for x in range(K + 1):
    for y in range(K + 1):
        z = S - x - y
        if z <= K and z >= 0:
            ans += 1

print(ans)

Measured memory_bytes: 3060
//Hello. I'm Peter.
#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<cctype>
#include<ctime>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int uin;
#define peter cout<<"i am peter"<<endl
#define input freopen("data.txt","r",stdin)
#define randin srand((unsigned int)time(NULL))
#define INT (0x3f3f3f3f)*2
#define LL (0x3f3f3f3f3f3f3f3f)*2
#define gsize(a) (int)a.size()
#define len(a) (int)strlen(a)
#define slen(s) (int)s.length()
#define pb(a) push_back(a)
#define clr(a) memset(a,0,sizeof(a))
#define clr_minus1(a) memset(a,-1,sizeof(a))
#define clr_INT(a) memset(a,INT,sizeof(a))
#define clr_true(a) memset(a,true,sizeof(a))
#define clr_false(a) memset(a,false,sizeof(a))
#define clr_queue(q) while(!q.empty()) q.pop()
#define clr_stack(s) while(!s.empty()) s.pop()
#define rep(i, a, b) for (int i = a; i < b; i++)
#define dep(i, a, b) for (int i = a; i > b; i--)
#define repin(i, a, b) for (int i = a; i <= b; i++)
#define depin(i, a, b) for (int i = a; i >= b; i--)
#define pi 3.1415926535898
#define eps 1e-9
#define MOD 1000000007
#define MAXN
#define N 50
#define M 4
int n;
int dp[N][M];
int p[N],t[N];
int main(){
//    input;
    while(~scanf("%d",&n) && n){
        repin(i,1,n){
            scanf("%d %d",p+i,t+i);
        }
        repin(i,1,n){
            repin(j,1,3){
                dp[i][j]=INT;
            }
        }
        if(p[1]<=t[1]){
            dp[1][1]=p[1];
        }
        else{
            printf("NG %d\n",1);
            continue;
        }
        repin(i,2,n){
            //for dp[i][1]
            repin(j,1,3){
                if(dp[i-1][j]!=INT){
                    if(t[i-1]+(j+1)*p[i-1]+1*p[i]<=t[i]){
                        dp[i][1]=min(dp[i][1],dp[i-1][j]+p[i-1]+p[i]);
                    }
                }
            }
            //for dp[i][2],dp[i][3]
            repin(j,2,3){
                if(dp[i-1][j-1]!=INT){
                    if(t[i-1]+j*abs(p[i]-p[i-1])<=t[i]){
                        dp[i][j]=min(dp[i][j],dp[i-1][j-1]+abs(p[i]-p[i-1]));
                    }
                }
            }
        }
        int mini=INT;
        repin(j,1,3){
            mini=min(mini,dp[n][j]);
        }
        if(mini==INT){
            int who=1;
            repin(i,1,n){
                bool ok=false;
                repin(j,1,3){
                    if(dp[i][j]!=INT){
                        ok=true;
                        break;
                    }
                }
                if(!ok){
                    who=i;
                    break;
                }
            }
            printf("NG %d\n",who);
        }
        else{
            mini+=p[n];
            printf("OK %d\n",mini);
        }
    }
}

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

using namespace std;

namespace {

#define VEVE(i, a, b) for (ll i = a, __##i = b; i < __##i; ++i)
#define DYDY(i, a, b) for (ll i = a, __##i = b; i > __##i; --i)
#define RARA(x, seq) for (auto &x : seq)
#define SIZE(x) ((ll)(x.size()))
#define ALL(x) x.begin(), x.end()

typedef int64_t ll;
typedef double dd;

ll Choose3(ll n) {
  return n * n * n;
}

void Solve(ll) {
  ll n, k;
  if (not(cin >> n >> k)) return;
  const ll zeros = n / k;
  const ll halfs = k % 2 == 0 and n >= k / 2 ? (max(ll(0), (n - k / 2) / k) + 1) : 0;
  const ll res = Choose3(zeros) + Choose3(halfs);
  cout << res << endl;
}

void Init() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
}
}

int32_t main() {
#ifdef AZN
  freopen("input.txt", "r", stdin);
#endif
  Init();
  ll tests = 11;
  VEVE(test, 1, tests + 1) Solve(test);
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ri(x) scanf("%d",&(x))
#define ri2(x,y) scanf("%d %d",&(x),&(y))
#define ri3(x,y,z) scanf("%d %d %d",&(x),&(y),&(z))
#define rll(x) scanf("%lld",&(x))
#define rll2(x,y) scanf("%lld %lld",&(x),&(y))
#define rll3(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z))
#define gc(x) ((x) = getchar())
using namespace::std;

const long double PI = acos(-1);
const long long MOD = 1000000000 +7;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> tll;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<tll> vtll;
typedef vector<string> vs;
typedef set<int> si;
typedef set<ii> sii;
typedef set<iii> siii;

ll gcd(ll a, ll b){ return b==0?a:gcd(b,a%b);}

ll add(ll a, ll b, ll m = MOD){
	return (a%m + b%m + m + m) % m;
}

ll mul(ll a, ll b, ll m = MOD){
	return ((a * b) % m + m) % m;
}

ll pow_mod(ll a, ll b, ll m = MOD){
	ll res = 1LL;
	a = a%m;
	while(b){
		if(b&1) res = mul(res,a,m);
		b >>= 1;
		a = mul(a,a,m);
	}
	return res;
}

ll fastexp(ll a, ll b){
	ll res = 1LL;
	while(b){
		if(b&1) res = res*a;
		b >>= 1;
		a *= a;
	}
	return res;
}

int gcdExtendido(int a, int b, int *x, int *y){
	if(a == 0){
		*x = 0;
		*y = 1;
		return b;
	}
	int x1, y1;
	int gcd = gcdExtendido(b%a,a,&x1,&y1);
	
	*x = y1-(b/a)*x1;
	*y = x1;
	return gcd;
}

int modInverso(int a, int m){
	int x, y;
	int g = gcdExtendido(a,m,&x,&y);
	if(g!=1) return -1;
	else return (x%m + m)%m;
}

/****************************************
*************P*L*A*N*T*I*L*L*A************
*****************************************/

const int N = 10000+5;

int n;
vector<int> a;

bool isIdenticallyNull(int p){
	vector<int> sum(min(n+1, p), 0);
	sum[0] = a[0] % p;
	for(int i=1; i<=n; i++){
		int pos = (i - 1) % (p - 1) + 1;
		sum[pos] = add(sum[pos], a[i], p);
	}
	for(int x : sum) if(x) return false;
	return true;
}

bool test(int p){
	if(isIdenticallyNull(p)) return true;
	return false;
}

bool primo(int x){
	for(int i = 2; i * i <= x; i++){
		if(x % i == 0) return false;
	}
	return true;
}

void solve(){
	vi ans;
	int x = abs(a[0]);
	for(int i = 1; i <= n; i++) x = gcd(x, abs(a[i]));
	for(int i = 2; i * i <= x; i++){
		if(x % i == 0){
			while(x % i == 0){
				x /= i;
			}
			if(test(i)) ans.emplace_back(i);
		}
	}
	if(x > 1 and test(x)) ans.emplace_back(x);
	for(int i = 2; i <= n; i++){
		if(primo(i) and test(i)) ans.emplace_back(i);
	}
	sort(all(ans));
	ans.erase(unique(all(ans)),ans.end());
	for(int i=0; i<ans.size(); i++){
		printf("%d\n",ans[i]);
	}
}

int main(){
	ri(n);
	a.resize(n+1);
	for(int i=n; i>=0; i--) ri(a[i]);
	solve();
	return 0;
}

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

const int MAXN = 500 + 3;
int H[MAXN][MAXN];
bool occ[MAXN][MAXN];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

void dfs(int x, int y) {
    int z = H[x][y] + occ[x][y];
    for (int t = 0; t < 4; t++) {
        int x1 = x + dx[t], y1 = y + dy[t];
        if (H[x1][y1] > z) {
            H[x1][y1] = z;
            dfs(x1, y1);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    
    for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) {
        H[i][j] = min(min(i, N+1-i), min(j, N+1-j)) - 1;
        occ[i][j] = true;
    }

    int res = 0;
    for (int it = 0; it < N*N; it++) {
        int id;
        cin >> id;
        int x = (id+N-1)/N;
        int y = id % N;
        if (y == 0) y += N;
        res += H[x][y];
        occ[x][y] = false;
        dfs(x, y);
    }
    cout << res << "\n";
    
}


Measured memory_bytes: 20196
H,W,K=map(int, input().split())
A=[]
for i in range(H):
  a=input()
  A.append(a)
  
import itertools
B=list(itertools.product([0,1], repeat=H))
C=list(itertools.product([0,1], repeat=W))
ans=0
for b in B:
  for c in C:
    cnt=0
    for i in range(H):
      for j in range(W):
        if A[i][j]=='#' and b[i]==0 and c[j]==0:
          cnt+=1
    if cnt==K:
      ans+=1
print(ans)
        

Measured memory_bytes: 9136
#include<iostream>

int H, W, K;
int dp[1001][1001][3];

int solve(int x1, int y1, int x2, int y2, int type){
	int res = 0;
	for(int y=y1;y<=y2;y++){
		res += dp[y][x2][type] - dp[y][x1-1][type];
	}
	return res;
}

int main(){
	std::cin >> H >> W >> K;
	for(int y=1;y<=H;y++){
		for(int x=1;x<=W;x++){
			char c;
			std::cin >> c;
			if(c == 'J')dp[y][x][0]++;
			if(c == 'O')dp[y][x][1]++;
			if(c == 'I')dp[y][x][2]++;
			for(int i=0;i<3;i++){
				dp[y][x][i] += dp[y][x-1][i];
			}
		}
	}

	while(K--){
		int x1, y1, x2, y2;
		std::cin >> y1 >> x1 >> y2 >> x2;
		std::cout << solve(x1, y1, x2, y2, 0);
		for(int t=1;t<3;t++){
			std::cout << " " << solve(x1, y1, x2, y2, t);
		}
		std::cout << "\n";
	}
}

Measured memory_bytes: 12780
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<fstream>

#define MOD (1000000007)

using namespace std;

typedef long long int Int;

constexpr Int TEN(int n) { return n == 0 ? 1 : 10 * TEN(n-1); }

vector<Int> s;
int N;
int main(void) {
    cin>>N;

    for(int i = 0;i < N;i++) {
        Int t;
        cin>>t;
        s.push_back(t);
    }

    Int ans = 0;
    for(int i = 1;i < N;i++) {
        int left = 0;
        int right = N-1;
        Int score = 0;
        while(1) {
            left += i;
            right -= i;
            if(left == right || right <= i || left-i == right)
                break;

            score += s[left] + s[right];
            ans = max(ans,score);
        }
    }

    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 1400
N = int(input())
S = input()

A = [0]*3

for s in S:
    if s == "R":
        A[0] += 1
    elif s =="G":
        A[1] += 1
    elif s == "B":
        A[2] += 1
        
ans = 1

for a in A:
    ans *= a

for i in range(N-1):
    for j in range(i+1, N):
        k = 2*j - i
        if(k >= N):
            continue
        if(S[j] != S[i] and S[j] != S[k] and S[i] != S[k]):
            ans -= 1
            
print(ans)

Measured memory_bytes: 73736
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(n) begin(n),end(n)
using ll = long long;
using P = pair<int,int>;

int main() {
    int n;
    cin >> n;
    vector<ll> a(n), b(n);
    ll cnt = 0;
    rep(i,n) cin >> a[i] >> b[i];
    for(int i = n-1; i >= 0; --i){
        a[i]+=cnt;
        if(a[i]%b[i]==0) continue;
        cnt += b[i]- a[i]%b[i];
        a[i] += cnt;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 4848
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 100000000000000

int main(){
	int n;cin>>n;
	string s;cin>>s;

	int left=0,right=0;

	for(int i=0;i<n;i++){
		if(s[i]=='('){left++;}//'(':left  ')':right
		else if(s[i]==')'){
			if(left>0){left--;}//()ができている部分は足す必要なし
			else{right++;}
		}
	}

	for(int i=0;i<right;i++){//right余り分だけleft出力
		cout<<'(';
	}
	cout<<s;
	for(int i=0;i<left;i++){//left余り分だけright出力
		cout<<')';
	}
	cout<<endl;

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#define N 100

int main(){
  int n,u,k,v,i,j;
  int G[N][N];
  for (i = 0 ; i < N ; i++) {
    for (j = 0 ; j < N ; j++) {
      G[i][j] = 0;
    }
  }
  scanf("%d",&n);
  for(i = 0 ; i < n ; i++){
    scanf("%d%d",&u,&k); u--;
    for(j = 0 ; j < k ; j++){
      scanf("%d",&v); v--;
      G[u][v] = 1;
    }
  }
  for(i = 0 ; i < n ; i++){
    for(j = 0 ; j < n ; j++){
      printf("%d%c",G[i][j],(j < n-1 ? ' ' : '\n'));
    }
  }
  return 0;
}



Measured memory_bytes: 2112
a,b,c,d,e,f=map(int,input().split())
w=[a*i+b*j for i in range(31) for j in range(31) if 0<a*i+b*j<=f//100]
m=max(w)*e//min(c,d)+1
s=[c*i+d*j for i in range(m) for j in range(m) if 0<c*i+d*j<=max(w)*e]
w=sorted(list(set(w)))
s=sorted(list(set(s)))
mx=0
res=(min(a,b),0)
for p in w:
	for q in s:
		if p*100+q>f or q/p>e:
			continue
		r=100*q/(100*p+q)
		if mx<r:
			mx=r
			res=(p,q)
p,q=res
print(100*p+q,q)

Measured memory_bytes: 56156
import math
Tre = []
num = 0
while True:
    li = list(map(int,input().split(",")))
    if li == [0,0]:
        break
    Tre.append(li)
    num += 1
x,y = 0,0
deg = 90
for i in range(num):
    x,y = x + Tre[i][0]*math.cos(math.pi*deg/180),y + Tre[i][0]*math.sin(math.pi*deg/180)
    deg = deg - Tre[i][1]
print(int(x))
print(int(y))

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

using namespace std;

int main(){
	int A,B;
	cin>>A>>B;
	int k;
	for(int i =0;i<100;i++)
	{	
		if(A*i - (i-1) >=B)
		{
			cout<<i;
			break;
		}
	}
}

Measured memory_bytes: 256
b = input().split()
n = int(b[0])
k = int(b[1])
r = 0
s=list(input())
for i in range(n-1):
    if(s[i] == s[i+1]):
        r += 1
t = n - r
if(k*2 < t):
    print(r + k*2)
else:
    print(n-1)

Measured memory_bytes: 4084
#include <bits/stdc++.h>
using namespace std;
using ll         = long long;
constexpr ll MOD = 1000000007;
#define REP(i, n) for (ll i = 0; i < (n); i++)
#define REP2(i, x, n) for (ll i = x; i < (n); i++)
#define PR(x) cout << (x) << "\n"
#define PS(x) cout << (x) << " "
const long long INF = numeric_limits<long long>::max();
int main() {
    ll N;
    cin >> N;
    map<ll, ll> values;
    REP(i, N) {
        ll n;
        cin >> n;
        values[n]++;
    }

    bool isOk = true;
    for (const auto& v : values) {
        isOk &= v.second == 1;
    }

    PR(isOk ? "YES" : "NO");
    return 0;
}

Measured memory_bytes: 16056
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
using namespace std;

typedef long long ll;

int main() {
	int n; cin >> n;
	bool dp[10002] = { 0 };
	dp[0] = true;
	for (int i = 0; i < n; ++i) {
		int s; cin >> s;
		for (int j = 10001; j >= 0; --j) {
			if (!dp[j]) continue;
			dp[j + s] = true;
		}
	}
	int ans = 0;
	for (int i = 0; i < 10002; ++i) {
		if (!dp[i] || i % 10 == 0) continue;
		ans = i;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
///...................................*****.................................................///
///        Author :  MD. Rakibul Islam ( mmdrakibul2912@gmail.com )                         ///
///                  Department of Computer Science                                         ///
///                  & Engineering,                                                         ///
///                  Comilla University , Bangladesh.                                       ///
///...................................*****.................................................///
#define SQR(n) (n*n)
#define CHR getchar()
#define NL printf("\n")
#define PI 2.0*acos(0.0)
#define ll              long long int
#define ull             unsigned long long int
#define sc              scanf
#define gcd(a,b)        __gcd(a,b)
#define lcm(a,b)        ((a)*(b))/gcd(a,b)
#define pf              printf
#define MOD             1000000007
#define mx              123456789
#define Max(a,b) ((a>b)?a:b)
#define Min(a,b) ((a<b)?a:b)
#define ff first
#define D double
#define sz size()
#define ss second
#define PB push_back
#define MP make_pair
#define all(a) a.begin(),a.end()
#define _Max(a,b,c) Max(a,Max(b,c))
#define _Min(a,b,c) Min(a,Min(b,c))
using namespace std;
int main()
{
    ll n, m, i, j, k, l;
    cin>>n>>m;
    if((n*500)>=m)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
 
typedef struct{
    int num[6];
}saikoro;
 
 
 
saikoro s_1,s_2;
 
void n(saikoro *a){
    int tmp;
    tmp=a->num[4];
    a->num[4]=a->num[0];
    a->num[0]=a->num[1];
    a->num[1]=a->num[5];
    a->num[5]=tmp;
}
 
void s(saikoro *a){
    int tmp;
    tmp=a->num[1];
    a->num[1]=a->num[0];
    a->num[0]=a->num[4];
    a->num[4]=a->num[5];
    a->num[5]=tmp;
}
 
void e(saikoro *a){
    int tmp;
    tmp=a->num[2];
    a->num[2]=a->num[0];
    a->num[0]=a->num[3];
    a->num[3]=a->num[5];
    a->num[5]=tmp;
}
 
void w(saikoro *a){
    int tmp;
    tmp=a->num[3];
    a->num[3]=a->num[0];
    a->num[0]=a->num[2];
    a->num[2]=a->num[5];
    a->num[5]=tmp;
}
 
int rota(saikoro *a){
    int tmp;
    tmp=a->num[1];
    a->num[1]=a->num[2];
    a->num[2]=a->num[4];
    a->num[4]=a->num[3];
    a->num[3]=tmp;
     
}
 
int check(){
    int i;
    for(i=0;i<6;i++){
        if(s_1.num[i]!=s_2.num[i]){
            return 1;
        }
    }
    return 0;
}
 
int main(){
    int i,j,k,f_br=0;
    char input[128];
     
    fgets(input,sizeof input,stdin);
    sscanf(input,"%d %d %d %d %d %d",&s_1.num[0],&s_1.num[1]
        ,&s_1.num[2],&s_1.num[3],&s_1.num[4],&s_1.num[5]);
     
    fgets(input,sizeof input,stdin);
    sscanf(input,"%d %d %d %d %d %d",&s_2.num[0],&s_2.num[1]
        ,&s_2.num[2],&s_2.num[3],&s_2.num[4],&s_2.num[5]);
     
     
     
     
    for(i=0;i<4;i++){
        for(j=0;j<4;j++){
            for(k=0;k<4;k++){
                if(check()==0){
                    f_br=1;
                    break;
                }
                rota(&s_1);
            }
            if(f_br==1){
                break;
            }
            e(&s_1);
        }
        if(f_br==1){
            break;
        }
        n(&s_1);
    }
     
    if(f_br==1){
        printf("Yes\n");
    }else{
        printf("No\n");
    }
     
    return 0;
}

Measured memory_bytes: 588
#include <stdio.h>
#define REP(a) for(i = 0; i < a; i++)
int main(void) {
    int i,n,count = 1,han = 0;
    scanf("%d",&n);
    int a[n];
    REP(n) {
        scanf("%d",&a[i]);
        if (a[i] % 2 != 0) {
            puts("0");
            goto end;
        }
    }
    while (1) {
        REP(n) {
            a[i] = a[i] / 2;
            if (a[i] % 2 != 0) {
                han = -1;
            }
        }
        if (han < 0) {
            printf("%d\n",count);
            break;
        }
        count++;
    }
end:
    return 0;
}

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

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

    int n;
    string s;
    cin >> n >> s;

    vector<vector<int>> dp(n, vector<int>(n));
    int lcs = 0;

    for (int i = 1; i < n; i++)
    {
        if (s[0] == s[i])
        {
            dp[0][i] = 1;
            if (0 + dp[0][i] > i)
            {
                dp[0][i] = 0;
            }
            else
            {
                lcs = 1;
            }
        }
    }

    for (int i = 1; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (s[i] == s[j])
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                if (i + dp[i][j] > j)
                {
                    dp[i][j] = 0;
                }
                else
                {
                    lcs = max(dp[i][j], lcs);
                }
            }
            else
            {
                dp[i][j] = 0;
            }
        }
    }

    cout << lcs << endl;
}


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

static const long long INF=1e15;

int main(){
    int N,M; cin >> N >> M;
    long long x[N],y[N],z[N];
    for(int i=0;i<N;i++){
        cin >> x[i] >> y[i] >> z[i];
    }
    long long dp[N+2][M+2];
    long long ans=-INF;
    for(int a=-1;a<2;a++){
        for(int b=-1;b<2;b++){
            for(int c=-1;c<2;c++){
                if(a==0||b==0||c==0) continue;
                for(int i=0;i<=N;i++){
                    for(int j=0;j<=M;j++){
                        dp[i][j]=-INF;
                    }
                }
                dp[0][0]=0;
                for(int i=0;i<N;i++){
                    for(int j=0;j<=M;j++){
                        long long v=a*x[i]+b*y[i]+c*z[i];
                        dp[i+1][j+1]=max(dp[i][j]+v,dp[i+1][j+1]);
                        dp[i+1][j]=max(dp[i][j],dp[i+1][j]);
                    }
                }
                ans=max(dp[N][M],ans);
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 8064
/*
Sharif Hasan - CSE, PUST
Apr 24, 2020 02: 14 PM
*/
#include<bits/stdc++.h>
#define br cout<<"\n"
#define what(x) cout<<"in here var= "<<x<<"\n";

/*STL definations*/
#define pb push_back

#define FOR(i,n) for(int i=0;i<n;i++)
#define FROM(a,i,n) for(int i=a;i<n;i++)
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;

int cnt[100001]={-1};
/*Main function*/
int main()
{
    long long n;long long sm=0;
    cin>>n;
    long long arr[n],cnt[100001]={0};
    FOR(i,n){
        cin>>arr[i];
        ++cnt[arr[i]];
        sm+=arr[i];
    }
    long long k;
    cin>>k;
    //cout<<sm<<endl;
    FOR(i,k){
        long long p,q;
        cin>>p>>q;
        if(cnt[p]!=0){
            long long reduced=cnt[p]*p;
            long long add=cnt[p];
           // cout<<p<<" r= "<<reduced<<" "<<add;br;
            cnt[p]=0;
            cnt[q]+=add;
            long long nxt=add*q;
            sm-=reduced;
           // cout<<sm<<" sm \n";
            sm+=nxt;
        }
        cout<<sm;br;
        
    }
    
    return 0;
}


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

using namespace std;

#define MAX_NODE 52


void dfs(bool graph[MAX_NODE][MAX_NODE], bool visited[], int n, int curr)
{
  //cout << curr+1 << endl;
  for(int i=0; i<n; i++){
    if(!visited[i] && graph[curr][i]){
      visited[i]=true;
      dfs(graph, visited, n, i);
    }
  } 
}


int main()
{
  int n, m;
  cin >> n >> m;  
  
  bool graph[MAX_NODE][MAX_NODE];
  bool visited[MAX_NODE];
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      graph[i][j] = false;
    }
    visited[i]=0;
  }
  
  for(int i=0; i<m; i++){
    int a, b;
    cin >> a >> b;
    graph[a-1][b-1] = true;
    graph[b-1][a-1] = true;
  }
  
  int count=0;
  for(int i=0; i<n; i++){
    for(int j=0; j < i; j++){
      if(graph[i][j]){
        graph[i][j]=false;
        graph[j][i]=false;

        //cout << "--cut " << i+1 << " " << j+1 << endl;
        visited[0]=true;
	    dfs(graph, visited, n, 0);
        
        int sum=0;
        for(int k=0; k<n; k++){
          if(visited[k]){
            sum++;
            visited[k]=0;
          }
        }
        if(sum!=n){
	        count++;
            //printf("--ok\n");
        }
        
        graph[i][j]=true;
        graph[j][i]=true;
      }
    }
  }
        
  cout << count << endl;

  return 0;
}


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

typedef long long ll;
typedef pair<int,int> ii;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	string s,t; cin>>s>>t;
	int l=t.size();
	for (int i=0; i<l; i++)
		cout << s[i] << t[i];
	if(s.size()!=l)
		cout << s[l];
	cout << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,N) for(int (i)=0;(i)<(N);++(i))
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define MP make_pair
#define pb push_back
const int INF = 1e9;
const int MOD = INF+7;
using P = pair<int,int>;

signed main(){
    int N,X;
    cin >> N >> X;
    vector<int> A(N);
    rep(i,N) cin >> A[i];

    vector<int> MIN(N,INF);
    int ans = (1LL<<62);

    rep(i,N){
        int s = 0;
        rep(j,N){
            MIN[j] = min(MIN[j],A[(N+j-i)%N]);
            s += MIN[j];
        }
        s += X*i;
        ans = min(ans,s);
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int main(){

	int n, m;
	cin >> n >> m;

	int nax1 = 0, nax2 = 1e9;

	for (int i = 0; i < m; i++) {
		int l, r;
		cin >> l >> r;
		nax1 = max(nax1, l);
		nax2 = min(nax2, r);
	}

	int ans = nax2 - nax1 + 1 ;

	if (ans < 1)  ans = 0;

	cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
# coding: utf-8
# パーティション


def partition(A, p, r):
    x = A[r]
    i = p - 1
    tmp = 0

    for j in range(p, r):
        if A[j] <= x:
            i = i + 1
            tmp = A[i]
            A[i] = A[j]
            A[j] = tmp
    tmp = A[i + 1]
    A[i + 1] = A[r]
    A[r] = tmp
    return i + 1


if __name__ == "__main__":
    n = int(input())

    A = [int(i) for i in input().split()]
    x = A[n - 1]
    p = partition(A, 0, n - 1)
    A = ['[' + str(v) + ']' if i == p else str(v) for i, v in enumerate(A)]
    print(' '.join(A))



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

int main()
{
	float A[101];
	float N;
	float tmp;
	
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> tmp;
		A[i] = 1 / tmp;
	}

	float sum = 0;
	for (int i = 0; i < N; i++)
	{
		sum += A[i];
	}

	cout << 1 / sum << endl;
}

Measured memory_bytes: 256
#include<cmath>
#include<iostream>
#include<algorithm>
#include <string>
#include <stdexcept>
using namespace std; 
int main(){
  int a,b,c,d,e;
   char g[3]; string h,i;
    cin >> a>>b;
 if((a*b)%2==0)cout <<"No";
  else cout <<"Yes";
  
}

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

#define MAXN 123123
#define INF 0x3f3f3f3f

long int n, w, weight[102], value[102], memo[102][MAXN];

long int knap(int i, int carry){
    if(carry>w) return -INF;
    if(i==n) return 0;
    if(memo[i][carry]!=-1) return memo[i][carry];

    return memo[i][carry] = max(knap(i+1, carry), knap(i+1, carry+weight[i])+value[i]);
}

int main(){
    cin >> n >> w;

    for(int i=0;i<n;i++){
        cin >> weight[i] >> value[i];
    }

    memset(memo, -1, sizeof memo);

    cout << knap(0, 0) << endl;
}


Measured memory_bytes: 98304
#!/usr/bin/env python3

N, M = map(int, input().split())
S = input()
T = input()

def gcd(x, y):
    if x < y:
        x, y = y, x

    if y == 0:
        return x

    else:
        return gcd(y, x % y)

nm = gcd(N, M)

if nm == 1:
    if S[0] == T[0]:
        print(N * M)
    else:
        print(-1)

else:
    sp = N // nm
    tp = M // nm

    si = 0
    ti = 0

    ans = True

    while (si < N and ti < M):
        if S[si] == T[ti]:
            si += sp
            ti += tp
        else:
            ans = False
            break

    if ans:
        print(N * M // nm)
    else:
        print(-1)

Measured memory_bytes: 9180
pub fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

pub fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

pub fn read_vec2<T: std::str::FromStr>(n: usize) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

pub fn read_col<T: std::str::FromStr>(n: usize) -> Vec<T> {
    (0..n).map(|_| read()).collect()
}

fn main() {
    let nc: Vec<usize> = read_vec();
    let n = nc[0];
    let c = nc[1];
    let dmat: Vec<Vec<u32>> = read_vec2(c);
    let cmat: Vec<Vec<usize>> = read_vec2(n);

    let mut cost: Vec<Vec<u32>> = vec![vec![0; c]; 3];

    for r in 0..3 {
        for k in 0..c {
            let mut tmp = 0;
            for i in 0..n {
                for j in 0..n {
                    if (i + j) % 3 == r {
                        tmp += dmat[cmat[i][j] - 1][k];
                    }
                }
            }
            cost[r][k] = tmp;
        }
    }

    let mut ans = 1000000000;

    for i in 0..c {
        for j in 0..c {
            for k in 0..c {
                if i == j || j == k || k == i {
                    continue;
                }
                let tmp = cost[0][i] + cost[1][j] + cost[2][k];
                if tmp < ans {
                    ans = tmp;
                }
            }
        }
    }

    println!("{}", ans);
}


Measured memory_bytes: 6396
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int A,B,C;
	cin>>A>>B>>C;
	for(int i=min(A,B);i>0;i--)
	{
		if(A%i==0&&B%i==0)
			C--;
		if(C==0)
		{
			cout<<i<<endl;
			return 0;
		}
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,cc,n) for(int i=cc;i<n;++i)
#define lrep(i,cc,n) for(long long i=cc;i<n;++i)
#define rrep(i,cc,n) for(long i=cc;i>n;--i)
using ll = long long;

int main() {
    int n, m;
    cin >> n >> m;
    ll cost = 0;
    vector<pair<ll, ll>> shop(n);
    rep(i, 0, n)cin >> shop[i].first >> shop[i].second;
    sort(shop.begin(), shop.end());
    rep(i, 0, n){
        if(m <= shop[i].second){
            cost += shop[i].first * m;
            cout << cost << endl;
            return 0;
        }else{
            cost += shop[i].first * shop[i].second;
            m -= shop[i].second;
        }
    }
}



Measured memory_bytes: 1792
#include<stdio.h>
#include<string.h>
#define LEN 100005

typedef struct pp{
  char name[100];
  int t;
}P;

P Q[LEN];
int head,tail,n;

void enqueue(P x){
  Q[tail]=x;
  tail = (tail+1)%LEN;
}

P dequeue(){
  P x = Q[head];
  head=(head+1)%LEN;
  return x;
}

int min(int a,int b){ return a < b ? a: b;}


int main(){

  int elaps=0,c;
  int i,q;
  P u;
  scanf("%d %d",&n,&q);
  for(i=1;i<=n;i++){
    scanf("%s",Q[i].name);
    scanf("%d",&Q[i].t);
  }
  head =1; tail=n+1;


  while( head !=tail){
    u=dequeue();
    c=min(q,u.t);
    u.t -= c;
    elaps += c;
    if(u.t>0) enqueue(u);
    else{
      printf("%s %d\n",u.name,elaps);
    }
  }

  return 0;
}

Measured memory_bytes: 10756
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;
int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int n,ma,mb;
    cin>>n>>ma>>mb;
    int a[n],b[n],c[n];
    int dp[n+1][401][401];
    for(int i=0;i<=n;i++)for(int j=0;j<=400;j++)for(int k=0;k<=400;k++)dp[i][j][k]=1e9;
    dp[0][0][0]=0;
    for(int i=0;i<n;i++){
        cin>>a[i]>>b[i]>>c[i];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<=400;j++){
            for(int k=0;k<=400;k++){
                if(dp[i][j][k]==1e9)continue;
                dp[i+1][j][k]=min(dp[i+1][j][k],dp[i][j][k]);
                dp[i+1][j+a[i]][k+b[i]]=min(dp[i+1][j+a[i]][k+b[i]],dp[i][j][k]+c[i]);
            }
        }
    }
    int ans=1e9;
    for(int i=1;i<=400;i++){
        for(int j=1;j<=400;j++){
            //cout << dp[n][i][j]<<" ";
            if(i*mb==j*ma)ans=min(ans,dp[n][i][j]);
        }
        //cout <<endl;
    }
    if(ans==1e9)ans=-1;
    cout<< ans<<endl;
    return 0;
}

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

#define pii pair<int,int>
#define pll pair<ll,ll>
#define eb emplace_back
#define ll long long
#define nl '\n'
#define deb(x) cerr<<#x" = "<<x<<nl
#define in() ( { int a ; scanf("%d",&a); a; } )

const int N = 3e5 + 9;
const int mod = 1e9 + 7;

ll yo(ll n)
{
    if(n<=0) return 0;
    return n*(n+1)/2;
}
map<ll, vector<pll> > mp;
int32_t main()
{
    int n=in(), a=in(), d=in();
    if(d==0){
        if(a==0) return cout<<1<<nl,0;
        cout<<n+1<<nl;
        return 0;
    }
    if(d<0) d=-d, a=-a;
    for(int k=0; k<=n; k++){
        ll l=yo(k-1);
        ll r=yo(n-1)-yo(n-k-1);
        ll p=1LL*k*a;
        ll st=(p%d+d)%d;
        l+=(p-st)/d;
        r+=(p-st)/d;
        if(l<=r) mp[st].eb(l, r);
    }
    ll ans=0;
    for(auto& x: mp){
        auto v=x.second;
        vector<pair<ll,int>> a;
        for(auto x: v) a.eb(x.first, 0), a.eb(x.second, 1);
        sort(a.begin(), a.end());
        int op=0;
        ll last=0;
        for(auto x: a){
            if(x.second&&op==1) ans+=x.first-last+1;
            if(x.second==0&&op==0) last=x.first;
            if(x.second) op--;
            else op++;
        }
    }
    cout<<ans<<nl;
    return 0;
}


Measured memory_bytes: 22144
#define NDEBUG

#include <unordered_map>
#include <functional>
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <utility>
#include <string>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <tuple>
#include <set>
#include <map>

// [0, max)
#define FOR0(var, max) for (sl (var) = 0; (var) < (max); ++(var))
// [min, max)
#define FORi(var, min, max) for (sl (var) = (min); (var) < (max); ++(var))
// [min, max)
#define FORi_INV(var, min, max) for (sl (var) = (max) - 1; (var) + 1 > (min); --(var))
#define FORITER(var, iter) for (auto (iter) = (var).begin(); (iter) != (var).end(); (iter)++)
#define FORITER_INV(var, iter) for (auto (iter) = (var).rbegin(); (iter) != (var).rend(); (iter)++)

// a < b < c
#define LTLT(a, b, c) (((a) < (b)) && ((b) < (c)))
// a <= b < c
#define LELT(a, b, c) (((a) <= (b)) && ((b) < (c)))
// a < b <= c
#define LTLE(a, b, c) (((a) < (b)) && ((b) <= (c)))
// a <= b <= c
#define LELE(a, b, c) (((a) <= (b)) && ((b) <= (c)))

#ifndef NDEBUG
#  define MASSERT(cond) m_assert(cond, __LINE__, #cond);
#else
#  define MASSERT(...)
#endif

using namespace std;

using uc = unsigned char;
using ui = unsigned int;
using ul = unsigned long long int;

using sc = signed char;
using si = signed int;
using sl = signed long long int;

using ld = long double;

void m_assert(const bool& cond, const sl& line, const char *condstr) {
  if (!cond) {
    cerr << "Assertion Failed: " << condstr << " at line " << line << endl;
    exit(1);
  }
}

static sl T1, T2, A1, A2, B1, B2;

void solve(void) {
  sl P = (A1 - B1) * T1;
  sl Q = (A2 - B2) * T2;
  if (P > 0) {
    P *= -1;
    Q *= -1;
  }
  if (P + Q == 0) {
    cout << "infinity" << endl;
  } else if (P + Q < 0) {
    cout << 0 << endl;
  } else {
    sl k = -P / (P + Q);
    sl r = -P % (P + Q);
    if (r != 0) {
      cout << 2 * k + 1 << endl;
    } else {
      cout << 2 * k << endl;
    }
  }
}

int main(void) {
  cin >> T1 >> T2;
  cin >> A1 >> A2;
  cin >> B1 >> B2;
  solve();
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cmath>
#include<climits>
#include<unordered_set>


using namespace std;


template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}


int main(){
    long S = 1000000007;
    int N, M;
    cin >> N >> M ;
    vector<int> A(M);
    for(int i = 0; i < M ; i++) cin >> A[i];
    unordered_set<int> a(M);
    for(auto x: A) a.insert(x);

    vector<long> dp(N+1,0);
    dp[0] = 1;
    for(int i = 0 ; i < N ; i++){
        for(int j = i + 1; j <=min(N,i+2);j++){
            if(a.count(j)) continue;

            dp[j] += dp[i];
            dp[j] %= S;

        }

       
    }

    cout << dp[N];



}

Measured memory_bytes: 5376
#include <stdio.h>
#define NUMBER (4)
#define ROW (3)
#define COLUMN (10)

int main(){
int i,j,k,n,b,f,r,v,data[NUMBER][ROW][COLUMN]={};
scanf("%d",&n);
for(i=0;i<n;i++){
   scanf("%d %d %d %d",&b,&f,&r,&v);
   data[b-1][f-1][r-1]=data[b-1][f-1][r-1]+v;
}
for(i=0;i<NUMBER;i++){
   for(j=0;j<ROW;j++){
      for(k=0;k<COLUMN;k++){
         printf(" %d",data[i][j][k]);
      }
      printf("\n");
   }
   if((i!=(NUMBER-1))){
      printf("####################\n");
   }
   }

return 0;
}

Measured memory_bytes: 612
#include<iostream>
#include<iomanip>
using namespace std;

int main(){
    int n;
    cin >> n;
    double a[n];
    for(int i=0;i<n;i++){
        cin >> a[i];
    }

    double ans = 0;
    for(int i=0;i<n;i++){
        ans += 1/a[i];
    }
    cout << setprecision(6) << 1/ans << endl;
}


Measured memory_bytes: 256
N,M=map(int,input().split())
xyz=[list(map(int,input().split()))for i in range(N)]
ans=0
for i in range(8):
    i=bin(i)[2:].zfill(3)
    k=[]
    for j in range(3):
        if i[j]=="0":
            k.append(1)
        else:
            k.append(-1)
    l=[k[0]*x+k[1]*y+k[2]*z for x,y,z in xyz]
    l.sort(reverse=True)
    ans=max(ans,sum(l[:M]))
print(ans)


Measured memory_bytes: 40304
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main()
{
    ll a,b,c,k;
    cin>>a>>b>>c>>k;
    ll s=0,a1,b1,c1;
    if(a>=k)
    {
        s=k;
    }
    else
    {
        a1=k-a;
        b1=a1-b;
        if(b1>=0)
            s=a-b1;

    }
    cout<<s<<endl;
    return 0;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define each(a,x) for(auto a : (x))
#define all(a) (a).begin(),(a).end()
#define chmin(a,b) ((a) = min((a),(b)))
#define chmax(a,b) ((a) = max((a),(b)))
#define in_range(x,l,r) ((l)<=(x) && (x)<(r))
#define printvec(a) rep(i,a) cout << a[i] << " \n"[i+1==(a).size()];
#define fs first
#define sc second
#define em emplace
#define eb emplace_back
#define sz size()
#define MP make_pair
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;

const ll INF = 1e8;
const D EPS = 1e-8;
const ll MOD = 1e9+7;

int dfs(int v, int p, int d, vi &used, const vector<vi> &g){
  if(g[v].size() == 0) return 0;

  if(used[v]>=0){
    if(used[v] == used[p]) return 1;
    else return 2;
  }
  used[v] = d;

  int ans = 2;
  for(int u : g[v]){
    if(u == p) continue;
    int tmp = dfs(u,v,1-d,used,g);
    ans = min(ans, tmp);
  }
  return ans;
}

int main(){
  ll n, m;
  cin >> n >> m;
  vector<vi> g(n);
  rep(i,m){
    int a,b;
    cin >> a >> b;
    a--; b--;
    g[a].eb(b); g[b].eb(a);
  }

  vl cnt(3,0);
  vi used(n,-1);
  rep(v,n){
    if(used[v]==-1){
      cnt[dfs(v,-1,0,used,g)]++;
    }
  }

  ll ans = 0;
  while(cnt[0]){
    ans += 2ll*n - 1ll;
    n--; cnt[0]--;
  }

  cout << ans + cnt[1]*cnt[1] + 2ll*cnt[1]*cnt[2] + 2ll*cnt[2]*cnt[2] << endl;
}


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


int main(){
    int n;
    string cmd;
    while(cin >> n && n){
        int res = 0;
        bool left = false, right = false, st = 0;
        for(int x = 0; x < n; x++){
            cin >> cmd;
            if(cmd == "lu"){
                left = true;
            }else if(cmd == "ld"){
                left = false;
            }else if(cmd == "ru"){
                right = true;
            }else if(cmd == "rd"){
                right = false;
            }
            if(left == right){
                if(left != st){
                    st = left;
                    res += 1;
                }
            }
        }
        cout << res << endl;
    }
    return 0;
}

Measured memory_bytes: 1208
#include<iostream>
#include<map>

using namespace std;
#define rep(i, n) for(int i=0; i<(n); i++)

int main(){

   string S;
   cin>> S;

   int n, w, s, e;
   n=w=s=e=0;
   for(int i=0; i<S.size(); i++){
      char c=S[i];
      n+=c=='N';
      w+=c=='W';
      s+=c=='S';
      e+=c=='E';
   }

   if(n==0||w==0||s==0||e==0){
      if(n==0&&s==0){
         if((w==0&&e!=0)||(w!=0&&e==0)){
            cout<< "No"<< endl;
         }else{
            cout<< "Yes"<< endl;
         }
      }else if(w==0&&e==0){
         if((n==0&&s!=0)||(n!=0&&s==0)){
            cout<< "No"<< endl;
         }else{
            cout<< "Yes"<< endl;
         }
      }else{
         cout<< "No"<< endl;
      }
   }else{
      cout<< "Yes"<< endl;
   }

   return 0;
}


Measured memory_bytes: 256
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#define df 0
typedef long int li;

class mono{
  li a;
  
public:
  // constructor
  mono(){ a=0; }
  mono(li p){ a=p; }
  // getter
  li get(){ return a; }
  // addition
  mono operator+(mono m){return a+m.a;};
  // print
  void print(){printf("%d",a);}
};

///  Segment Tree  (prototype)  ///
template<typename Monoid>
class SegTree{
  int n;
  vector<Monoid> node;
  
public:
  int parent(int a){return (a-1)/2;}
  int  left(int a) {return (a*2+1);}
  int right(int a) {return (a*2+2);}
  int leaf(int a){return (a+n-1);}
  SegTree(vector<Monoid> v);
  SegTree(int k);
  void update(int i,Monoid x);
  Monoid find(int a,int b,int i,int l,int r);
  Monoid find(int a,int b){return find(a,b,0,0,n);}
  Monoid find(int a){return node.at(leaf(a));}
  void print(){
    for(int i=leaf(0);i<2*n-1;i++){
      printf(" %d:",i-leaf(0));
      node.at(i).print();
    }
    printf("\n");
  }
};
///  Segment Tree  ///

int main(){
  if(df) printf("*debug mode*\n");
  int n,k; cin >>n >>k;
  int a[n];
  for(int& x:a){
    cin >>x;
    x-=k;
  }
  if(df)for(int x:a)printf("%d ",x);
  if(df)printf(":a\n");
  li s[n+1];
  s[0]=0;
  map<li,int> sq;
  sq[0]++;
  if(df)printf("0 ");
  for(int i=0;i<n;i++){
    s[i+1]=s[i]+a[i];
    sq[s[i+1]]++;
    if(df)printf("%d ",s[i+1]);
  }
  if(df)printf(":s(1~)\n");
  int i=0;
  for(pair<const li,int>& p:sq){
    p.second=i++;
    if(df)printf("%d->%d  ",p.first,p.second);
  }
  if(df)printf(":squeeze\n");


  li cnt=0;
  SegTree<mono> sgt(sq.size());
  for(li x: s){
    if(df)printf("cnt(%d)",x);
    x=sq[x];
    if(df) sgt.find(0,x+1).print();
    cnt+=sgt.find(0,x+1).get();
    sgt.update(x,(mono)1+sgt.find(x));
    if(df)sgt.print();
  }
  cout << cnt;
}
///  Segment Tree  (main)  ///
template<typename Monoid>
SegTree<Monoid>::SegTree(vector<Monoid> v){
  int sz=v.size();
  n=1; while(n<sz)n*=2;
  node.resize(2*n-1);
  for(int i=0;i<v.size();i++){
    node.at(i+n-1)=v.at(i);
  }
  for(int i=n-2;i>=0;i--){
    node.at(i)=node.at(this->left(i))+node.at(right(i));
  }
}
template<typename Monoid>
SegTree<Monoid>::SegTree(int k){
  int sz=k;
  n=1; while(n<sz)n*=2;
  node.resize(2*n-1);
}

template<typename Monoid>
void SegTree<Monoid>::update(int i,Monoid x){
  i=this->leaf(i);
  node.at(i)=x;
  while(i>0){
    i=this->parent(i);
    node.at(i)=node.at(this->left(i))+node.at(this->right(i));
  }
}
template<typename Monoid>
Monoid SegTree<Monoid>::find(int a,int b,int i,int l,int r){
  Monoid x;
  if(r<=a || b<=l)return x;
  if(a<=l && r<=b)return node.at(i);
  Monoid m1=find(a,b,this->left(i) ,l,(l+r)/2);
  Monoid m2=find(a,b,this->right(i),(l+r)/2,r);
  x=m1+m2;
  return x;
}
///  Segment Tree  ///

/// confirm df==0 ///


Measured memory_bytes: 19200
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <climits>
#include <cmath>
#include <functional>
#include <map>
#include <queue>
#include <set>

#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define INF 999999999
#define size_t unsigned long long
#define ll long long
#define rep(i,a) for(int i=0;i<(a);i++)
#define repr(i,a) for(int i=(int)(a)-1;i>=0;i--)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FORR(i,a,b) for(int i=(int)(b)-1;i>=a;i--)
#define ALL(a) a.begin(), a.end()
using namespace std;
int si() { int x; scanf("%d", &x); return x; }
long long sl() { long long x; scanf("%lld", &x); return x; }
string ss() { string x; cin >> x; return x; }
void pi(int x) { printf("%d ", x); }
void pl(long long x) { printf("%lld ", x); }
void pd(double x) { printf("%.15f ", x); }
void ps(const string &s) { printf("%s ", s.c_str()); }
void br() { putchar('\n'); }

const int MOD = 1e9 + 7;

struct mint {
    int n;
    mint(int n_ = 0) : n(n_) {}
};

mint operator+(mint a, mint b) { a.n += b.n; if (a.n >= MOD) a.n -= MOD; return a; }
mint operator-(mint a, mint b) { a.n -= b.n; if (a.n < 0) a.n += MOD; return a; }
mint operator*(mint a, mint b) { return (long long)a.n * b.n % MOD; }
mint &operator+=(mint &a, mint b) { return a = a + b; }
mint &operator-=(mint &a, mint b) { return a = a - b; }
mint &operator*=(mint &a, mint b) { return a = a * b; }

int main () {
  int n;
  cin >> n;
  std::vector<int> d(n);
  rep(i,n) cin >> d[i];
  VSORT(d);
  cout << d[n/2] - d[n/2 - 1] << endl; 
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std ;
	#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	#define lli long long int
	#define ulli unsigned long long int
	#define ff first
	#define ss second
	#define mp make_pair
	#define pb push_back
	#define pf pop_front()
	#define lb lower_bound
	#define ub upper_bound
	#define bs binary_search
	#define loop(i,a,b) for(lli i=a;i<b;i++)
	#define loopi(i,a,b) for(int i=a;i<b;i++)
	#define all(v) v.begin(), v.end()
	#define mod 1000000007
	#define inf 100000000000000000
	#define lld long double
	#define pll pair<long long int,long long int>
	#define pii pair<int,int>
	#define vll vector<lli>
	#define vii vector<int>
	#define endl '\n'
	#define setp(k, x) fixed << setprecision(k) << (x)
	#define deb(x) cerr << #x << ": " << x << " " << endl;
	#define debug(x) cout << "m here-" <<#x<<" ..."<<"\n";
	#define printa(a,n) for(lli i=0;i<n;i++) cout<<a[i]<<" "; cout<<"\n";
  #define printv(a) for(lli i=0;i<a.size();i++) cout<<a[i]<<" "; cout<<"\n";
	bool sortcol( const vector<lli>& v1, const vector<lli>& v2 ) //sort on basis of column //use- sort(vect.begin(), vect.end(),sortcol);
      { return v1[1] < v2[1]; }//[] o based indexing in column
	bool sortpair(const pair<lli, lli> &a, const pair<lli, lli> &b)
			{return a.second < b.second;}


int main ()
{
	// fastio
 	// lli  t;
 	// cin>>t;
 	// while(t--)
 	{
		lli n,i,d,a,b,c,j,k,sum=0;
    double r;
    cin>>n>>a;
    for(i=0;i<a;i++)
    {
      cin>>b;
      sum+=b;
    }
    if(sum>n)
      cout<<"-1"<<"\n";
    else
        cout<<n-sum<<"\n";


 	}
}


Measured memory_bytes: 3624