akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
typedef pair<string, int> P;
map<string, int> m;
int d[] = { 1, -1, 4, -4 };

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

	queue<P> q;
	q.push(P("01234567", 0));
	m["01234567"] = 0;
	while(!q.empty()) {
		P p = q.front();
		q.pop();
		string s = p.first;
		
		for(int i = 0; i < 8; i++) {
			if(s[i] != '0') continue;
			for(int j = 0; j < 4; j++) {
				if(i + d[j] < 0 || 8 <= i + d[j]) continue;
				if(i == 3 && d[j] == 1 || i == 4 && d[j] == -1) continue;

				swap(s[i], s[i + d[j]]);

				if(m.find(s) == m.end() || p.second + 1 < m[s]) {
					m[s] = p.second + 1;
					q.push(P(s, p.second + 1));
				}

				swap(s[i], s[i + d[j]]);
			}
		}
	}

	string s;
	while(getline(cin, s)) {
		string ss;
		for(int i = 0; i < 8; i++) {
			ss += s[2 * i];
		}
		cout << m[ss] << endl;
	}
}

Measured memory_bytes: 3452
#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=(a);i<(b);i++)
#define qi queue<int>
#define vi vector<int>
#define ll long long
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define pii pair<int,int>
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define fi first
#define se second 
#define prq priority_queue
#define foreach(it,c) for(__typeof((c).begin()) it=c.begin();it!=c.end();it++)
//#define KEY_DOWN(VK_NONAME) ((GetAsyncKeyState(VK_NONAME) & 0x8000) ? 1:0)
using namespace std;
inline ll read(){
	ll x=0;
	int f=1;
	char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-')f=-f;
	for(;isdigit(c);c=getchar())x=x*10+(c-'0');
	return x*f;
}
inline void out(int x){
	if(x>=10)out(x/10);
	putchar(x%10+'0');
}
int main(){
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	int a,b,c,k;
	cin>>a>>b>>c>>k;
	if(k<=a+b)cout<<min(a,k)<<endl;
	else cout<<a-(k-a-b)<<endl;
	return 0;
}


Measured memory_bytes: 3676
#include <bits/stdc++.h>
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#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 all(x) (x).begin(),(x).end()
 
using namespace std;
using ll = long long;
 
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

struct edge { int to; int cost; };
 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> P;
 
const int INF = 1e9;
const int MOD = 1e9+7;
const double EPS = 1.0e-10;
const double PI = acos(-1.0);
 
const int mx4[] = {0,1,0,-1};
const int my4[] = {1,0,-1,0};
const int mx8[] = {0,1,1,1,0,-1,-1,-1};
const int my8[] = {1,1,0,-1,-1,-1,0,1};

int main() {
	int x,y,a,b,c;
	cin >> x >> y >> a >> b >> c;
	vi p(a),q(b),r(c);
	vector<P> v;
	rep(i,a) { cin >> p[i]; v.push_back(P(p[i],0));};
	rep(i,b) { cin >> q[i]; v.push_back(P(q[i],1));};
	rep(i,c) { cin >> r[i]; v.push_back(P(r[i],2));};
	sort(all(v)); reverse(all(v));
	ll sum = 0;
	int i = 0,cx = 0,cy = 0,cz = 0;
	while(cx+cy+cz < x+y){
		switch(v[i].second){
		case 0:
			if(cx < x){
				sum += v[i].first;
				cx++;
			}
			break;
		case 1:
			if(cy < y){
				sum += v[i].first;
				cy++;
			}
			break;
		case 2:
			if(cz < c){
				sum += v[i].first;
				cz++;
			}
			break;
		}
		i++;
	}
	cout << sum << endl;

	return 0;
}

Measured memory_bytes: 7664
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 200010
int cnt[MAXN],a[MAXN],A[MAXN];
int n,m,x,y,ans;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&A[i]);
		a[max(0,A[i]-cnt[A[i]])]++;
		cnt[A[i]]++;
	}
	for(int i=1;i<=n;i++)
		if(!a[i]) ans++;
	while(m--)
	{
		scanf("%d%d",&x,&y);
		int k=max(0,A[x]-cnt[A[x]]+1);
		if(k&&a[k]==1) ans++;
		a[k]--;
		cnt[A[x]]--;
		A[x]=y;
		k=max(0,A[x]-cnt[A[x]]);
		if(k&&a[k]==0) ans--;
		a[k]++;
		cnt[A[x]]++;
		printf("%d\n",ans);
	}
}

Measured memory_bytes: 3712
n, m = map(int, input().split())
a = set([int(input()) for _ in range(m)])

s = [1]*(n+1)

if 1 in a:
    s[1] = 0

for i in range(n-1):
    if i+2 in a:
        s[i+2] = 0
        continue
    s[i+2] = (s[i+1] + s[i]) % (10**9+7)
    
print(s[-1])

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

int main(){
  string a;
  cin >> a;
  int b;
  b = a.size() - 1;
  if (a.at(b) == 's'){
    cout << a << "es" << endl;
  }
  if (a.at(b) != 's'){
    cout << a << "s" << endl;
  }
}

Measured memory_bytes: 3624
#include<iostream>
using namespace std;
#include<bits/stdc++.h>
int p=1e9+7;
int dp[22][1<<22+1];
int solve(int arr[][21],int i,int s,int n)
{
      if(i==n)
      {
          if(__builtin_popcount(s)==n)
             return 1;
             return 0;
      }
  if(dp[i][s]!=-1)
    return dp[i][s];
    dp[i][s]=0;
    for(int j=0;j<n;j++)
    {     
        
         if(!((1<<j)&s)&&arr[i][j])
         {    
             dp[i][s]=(dp[i][s]+solve(arr,i+1,s|(1<<j),n))%p;
         }
    }
    return dp[i][s];

}
int main()
{
    memset(dp,-1,sizeof(dp));
    int n;
    cin>>n;
    int arr[21][21]={0};
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
          cin>>arr[i][j];
    }
   int s=0;
   int x1= solve(arr,0,s,n);
   cout<<x1<<endl;






}

Measured memory_bytes: 721152
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

const int MOD = 1e9 + 7;
const int iINF = 1000000000;
const long long int llINF = 1000000000000000000;
#define rep(n) for (ll i = 0; i < (n); i++)

using namespace std;
using ll = long long int;
using P = pair<int, int>;
using edge = struct {
  int to;
  int cost;
};

void comb(vector<vector<ll>> v) {
  for (ll i = 0; i < v.size(); i++) {
    v[i][0] = 1;
    v[i][i] = 1;
  }
  for (ll k = 1; k < v.size(); k++) {
    for (ll j = 1; j < 1 + (k / 2); j++) {
      v[k][j] = (v[k - 1][j - 1] + v[k - 1][j]);
    }
  }
}
ll c(ll n, ll r) {
  if (r * 2 > n)
    r = n - r;
  ll dividend = 1;
  ll divisor = 1;
  for (ll i = 1; i <= r; ++i) {
    dividend *= (n - i + 1);
    divisor *= i;
  }
  return dividend / divisor;
}

int main() {
  ll n, tmp;
  vector<ll> a;
  cin >> n;
  rep(n) {
    cin >> tmp;
    a.push_back(tmp);
  }

  sort(a.begin(), a.end());
  ll max = a.back();
  a.erase(a.begin() + n - 1);
  ll mid = -1;
  for (ll i = 0; i < n - 1; i++) {
    if (a[i] >= (long double)(max / 2)) {
      if (i == 0) {
        mid = a[i];
        break;
      } else if (a.size() == 1) {
        mid = a[i];
        break;
      } else if (a[i - 1] <= ((long double)max / 2) &&
                 (((long double)max / 2) - (long double)a[i - 1]) >
                     ((long double)a[i] - (long double)(max / 2))) {
        mid = a[i];
        break;
      } else {
        mid = a[i - 1];
        break;
      }
    }
  }
  if (mid == -1) {
    mid = a.back();
  }
  cout << max << " " << mid << endl;
  return 0;
}


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

int main(){
  int n,k,c=0,a=1;cin>>n>>k;
  while(a<k&&c<n){
    a*=2;
    c++;
  }
  while(c<n){
    a+=k;
    c++;
  }
  cout<<a;
}

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




























int main () {
    int64_t N, D;
    cin >> N >> D;
    
    int64_t count = 0;
    for (int64_t i = 0; i < N; i++) {
        int64_t a, b;
        cin >> a >> b;
        if (a * a + b * b <= D * D) {
            count++;
        }
    }
    cout << count << endl;

}

Measured memory_bytes: 3644
#include <iostream>
#include <utility>
#include <queue>
using namespace std;
typedef pair<int, int> P;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
int d[803][803];
char a[803][803];

int main()
{
    int h, w, k;
    cin >> h >> w >> k;
    int sx, sy;
    for(int i = 0; i < h; i++) for(int j = 0; j < w; j++){
        cin >> a[i][j];
        if(a[i][j] == 'S') sx = i, sy = j;
    }
    for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) d[i][j] = -1;
    queue<P> que;
    d[sx][sy] = 0;
    que.push(P(sx, sy));
    while(que.size()){
        P now = que.front();
        int x = now.first, y = now.second;
        que.pop();
        for(int i = 0; i < 4; i++){
            if(x + dx[i] >= 0 && x + dx[i] < h && y + dy[i] >= 0 && y + dy[i] < w &&
               d[x + dx[i]][y + dy[i]] == -1 && a[x + dx[i]][y + dy[i]] == '.' && d[x][y] < k){
                d[x + dx[i]][y + dy[i]] = d[x][y] + 1;
                que.push(P(x + dx[i], y + dy[i]));
            }
        }
    }
    int les = 1000000;
    for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) if(d[i][j] != -1)
        les = min(les, min(min(i, j), min(h - 1 - i, w - 1 - j)));
    cout << (les + k - 1) / k + 1 << endl;
}


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

typedef long long ll;
typedef unsigned long long ull;

int main()
{
    ll N, M, K;
    cin >> N >> M >> K;
    bool res = K==0;
    for(ll i = 0; i < N; i++){
        for(ll j = 0; j < M; j++){
            if(i*j+(N-i)*(M-j)==K) res = true;
            if(res) break;
        }
        if(res) break;
    }
    if(res){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int a[n];
	int b[n];
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		b[a[i]-1]=i+1;
	}
	for(int i=0;i<n;i++)
	{
		cout<<b[i]<<' ';
	}
}

Measured memory_bytes: 1536
"""
N=int(input())

print(800*N-int(N/15)*200)
"""
"""
N=int(input())
S=input()

max_n=0
temp=0
for strng in S:
	if strng=="I":
		temp+=1
		if max_n<temp:
			max_n=temp
	else:
		temp-=1
print(max_n)
"""
N=int(input())

Q=1000000007
p=1
for i in range(1,N+1):
	p*=i
	p=p%Q
print(p%Q)

Measured memory_bytes: 3060
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        String str;
        int i,j,a,b;
        int x[][];
        str = scan.nextLine();
        String[] num = str.split(" ", 0);
        a = Integer.valueOf(num[0]);
        b = Integer.valueOf(num[1]);
        x = new int[a+1][b+1];
       for(i=0;i<a;i++){
           str = scan.nextLine();
           num = str.split(" ", 0);
           for(j=0;j<b;j++){
               x[i][j] = Integer.valueOf(num[j]);
               x[i][b] += x[i][j];
               x[a][j] += x[i][j];
               x[a][b] += x[i][j];
           }
       }
        for(i=0;i<a+1;i++){
            for(j=0;j<b;j++){
                System.out.print(x[i][j]+" ");
            }
            System.out.println(x[i][j]);
        }


        scan.close();
    }

}



Measured memory_bytes: 32044
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <deque>
#include <algorithm>
#include <iomanip>
#include <functional>
#include <numeric>
#include <sstream>

#define REP(i, n) for(int i = 0;i < (n); i++)
#define REP2(i, x, n) for(int i = (x); i < (n); i++)
#define RREP(i, n) for (int i = (n) -1;i >= 0; i--)

#define ALL(a) (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define DESCSORT(c) sort(c.begin(), c.end(), greater<int>())

#define LL long long int
#define LD long double

#define PI 3.14159265358979

using namespace std;

//================================================

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

	int ans = 0;
	string S;
	while(cin >> S) {

		vector<string>Svec;
		REP(i, S.size()) {
			string tmp;
			tmp = S[i];
			Svec.push_back(tmp);
		}

		vector<string>Sreverse;
		Sreverse = Svec;
		reverse(ALL(Sreverse));

		if (Svec == Sreverse) {
			ans++;
		}
	}

	cout << ans << "\n";
	return 0;
}

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

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  char s;cin>>s;
  if(s=='A')cout<<'T'<<endl;
  else if(s=='C')cout<<'G'<<endl;
  else if(s=='G')cout<<'C'<<endl;
  else cout<<'A'<<endl;
  return 0;
  }


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

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

  char pre='*',prepre='*';
  rep(i,s.size()){
    if(s[i]==pre){
      cout<<i<<' '<<i+1<<endl;
      return 0;
    }
    if(s[i]==prepre){
      cout<<i-1<<' '<<i+1<<endl;
      return 0;
    }
    prepre=pre;
    pre=s[i];
  }
  cout<<-1<<' '<<-1<<endl;
  return 0;
}


Measured memory_bytes: 3756
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX 2000000
#define INFTY (1<<30)

int H, A[MAX+1];

int left(int i) { return i*2; }
int right(int i) { return i*2+1; } 

void maxHeapify(int i) {
    int l = left(i);
    int r = right(i);
    int largest;
    
    if(l<=H && A[l] > A[i]) largest = l;
    else largest = i;
    if(r<=H && A[r] > A[largest]) largest = r;
    
    if (largest != i) {
        swap(A[i], A[largest]);
        maxHeapify(largest);
    }
}

int extract() {
    int maxv;
    if (H<1) return -INFTY;
    maxv = A[1];
    A[1] = A[H--];
    maxHeapify(1);
    return maxv;
}

void increaseKey(int i, int key) {
    if(key < A[i]) return;
    A[i] = key;
    while(i>1 && A[i/2] < A[i]) {
        swap(A[i], A[i/2]);
        i /= 2;
    }
}

void insert(int key) {
    H++;
    A[H] = -INFTY;
    increaseKey(H, key);
}

int main() {
    int key;
    char com[10];
    
    while(1) {
        scanf("%s", com);
        if (com[0] == 'e' && com[1] == 'n') break;
        if (com[0] == 'i') {
            scanf("%d", &key);
            insert(key);
        } else {
            printf("%d\n", extract());
        }
    }
    
    return 0;
}


Measured memory_bytes: 6608
/*
 ____________________________________________________________
|                                                            |
|                   Author: ay2306                           |
|____________________________________________________________|

*/
#include <bits/stdc++.h>
//For ordered_set
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define MOD 1000000007
#define test int t; cin>>t; while(t--)
#define init(arr,val) memset(arr,val,sizeof(arr))
#define loop(i,a,b) for(int i=a;i<b;i++)
#define loopr(i,a,b) for(int i=a;i>=b;i--)
#define loops(i,a,b,step) for(int i=a;i<b;i+=step)
#define looprs(i,a,b,step) for(int i=a;i>=b;i-=step)
#define ull unsigned long long int
#define ll long long int
#define P pair
#define PLL pair<long long, long long>
#define PII pair<int, int>
#define PUU pair<unsigned long long int, unsigned long long int>
#define L list
#define V vector
#define D deque
#define ST set
#define MS multiset
#define M map
#define UM unordered_map
#define mp make_pair
#define pb push_back
#define pf push_front
#define MM multimap
#define F first
#define S second
#define IT iterator
#define RIT reverse_iterator
#define FAST ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define FILE_READ_IN freopen("input.txt","r",stdin);
#define FILE_READ_OUT freopen("output.txt","w",stdout);
#define all(a) a.begin(),a.end()
#define ord_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
// For ordered_set
using namespace __gnu_pbds;
const ll maxn = 1e5;

int main(){
    int n,k;
    cin >> n >> k;
    string a;
    cin >> a;
    a[k-1]+=32;
    cout << a;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
using namespace std;
int main() {
	int a, b;
	cin >> a;
	cin >> b;
	if (a <= 5) {
		cout << 0;
	}
	else if (a <= 12) {
		cout << b / 2;
	}else{
		cout << b;
	}

	return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main() {
	int S;
	cin >> S;
	int h;
	int m;
	int s;
	h = S / 3600;
	m = S % 3600 / 60;
	s = S % 3600 % 60;
	cout << h << ":" << m << ":" << s << endl;

	
	
}


Measured memory_bytes: 3120
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T,class U> using P = pair<T,U>;
template<class T> using vec = vector<T>;
template<class T> using vvec = vector<vec<T>>;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
 
int main(){
    int k;
    cin >> k;
    vec<int> lis = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    cout << lis[k-1] << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

std::vector<std::vector<LL>>G1, G2;
std::set<std::pair<LL, LL>>path;
std::vector<bool>vis;
std::vector<LL>outs;
std::vector<std::pair<LL, LL>>ans;

void dfs1(LL v)
{
	for (LL u : G1[v])
	{
		if (!vis[u])
		{
			path.insert(std::make_pair(v, u));
			vis[u] = true;
			dfs1(u);
		}
	}
}

void dfs2(LL v, LL p)
{
	if (vis[v]) return;
	vis[v] = true;
	for (LL u : G2[v]) dfs2(u, v);
	if (p != -1)
	{
		if (outs[v] % 2 == 0)
		{
			++outs[p];
			ans.push_back(std::make_pair(p, v));
		}
		else
		{
			++outs[v];
			ans.push_back(std::make_pair(v, p));
		}
	}
}

int main()
{
	LL N, M;
	in >> N >> M;
	std::vector<LL>A(M), B(M);
	rep(i, M) in >> A[i] >> B[i];

	if (M % 2 == 1)
	{
		out << -1 << std::endl;
		return 0;
	}

	G1.resize(N + 1);
	vis.resize(N + 1);
	rep(i, M)
	{
		G1[A[i]].push_back(B[i]);
		G1[B[i]].push_back(A[i]);
	}
	vis[1] = true;
	dfs1(1);

	G2.resize(N + 1);
	vis.clear(); vis.resize(N + 1);
	outs.resize(N + 1);
	rep(i, M)
	{
		auto it1 = path.find(std::make_pair(A[i], B[i]));
		auto it2 = path.find(std::make_pair(B[i], A[i]));
		if (it1 != path.end()) G2[A[i]].push_back(B[i]);
		else if (it2 != path.end()) G2[B[i]].push_back(A[i]);
		else
		{
			++outs[A[i]];
			ans.push_back(std::make_pair(A[i], B[i]));
		}
	}
	dfs2(1, -1);

	rep(i, ans.size()) out << ans[i].first << " " << ans[i].second << std::endl;
}


Measured memory_bytes: 31984
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
void inline solve()
{
    ll n;
    cin>>n;
    ll a[n];
    ll f=1;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        if(a[i]&1)
            f=0;
    }
    if(f)
    {
        ll ans=1e18;
        for(int i=0;i<n;i++)
        {
            ll c=0;
            while(a[i]>0 and !(a[i]&1))
            {
                a[i]=a[i]/2;
                c++;
            }
            ans=min(c,ans);
        }
        cout<<ans<<endl;
    }
    else
        cout<<0<<endl;


}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}


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

int main()
{
    int n, m;
    cin >> n >> m;
    int ans = 0;
    if (n > 1) ans += n * (n - 1) / 2;
    if (m > 1) ans += m * (m - 1) / 2;
    cout << ans << "\n";
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String [] args) {
		Scanner stdIn = new Scanner(System.in);
		int h, m, s;
		int S = stdIn.nextInt();
		
		while(S < 0 || S >= 86400) {
			S = stdIn.nextInt();
		}
		m = S / 60;
		h = m / 60;
		s = S - m * 60;
		m -= h * 60;
		
		System.out.println(h + ":" + m + ":" + s);
	}
}



Measured memory_bytes: 26412
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define ll long long
#define cst first
#define dur second
#define IO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
const int N = 1e5 + 5, M = 2 * N + 5;

int main(){
    int a, b;
    scanf("%d%d", &a, &b);
    a += b;
    if(a & 1)
        puts("IMPOSSIBLE");
    else printf("%d\n", a / 2);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
#define repr(i, a, b) for (int i = a; i >= (b); --i)
#define bit(n) (1LL << (n))
#define len(x) ((ll)(x).size())
#define debug(var) cout << "[" << #var << "]\n" << var << endl
#define int long long
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1000000007;
const double EPS = 1e-9;

template <typename T>
ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size();
  for (int i = 0; i < len; ++i) {
    s << v[i];
    if (i < len - 1)
      s << ' ';
  }
  return s;
}

template <typename T>
ostream& operator<<(ostream& s, const vector<vector<T>>& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) {
    s << vv[i];
    if (i != len - 1)
      s << '\n';
  }
  return s;
}

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;
}

__attribute__((constructor)) void initial() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
}

template <class T>
T find_max(T l, T r, bool f(T)) {
  T c;
  while (r - l > 1) {
    c = (r + l) / 2;
    if (f(c)) {
      l = c;
    } else {
      r = c;
    }
  }

  return l;
}

int N, M;
int V, P;
vector<int> A;


bool f(ll i) {
  if (i + 1 <= P)
    return true;

  vector<int> temp(i + 1 - P);
  rep(j, i + 1 - P) {
    temp[j] = A[i - 1 - j] - A[i];
  }

  int sum = 0, mx = 0;
  for (auto elem : temp) {
    sum += elem;
    chmax(mx, elem);
  }

  return (mx <= M && sum <= M * V);
}

signed main() {
  cin >> N >> M;
  cin >> V >> P;

  V = N - V;

  A = vector<int>(N);

  rep(i, N) {
    cin >> A[i];
  }
  sort(all(A), greater<int>());

  int ans = find_max(0LL, N, f) + 1;
  cout << ans << endl;
}

Measured memory_bytes: 1832
#include<bits/stdc++.h>
using namespace std;
const int N =2e5+100;
typedef long long ll;
int main()
{
    int n,k,x[N] ={0};
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)
        scanf("%d",&x[i]);
    sort(x,x+n);
    
    ll sum =0;
    for(int i=0;i<n-k;i++)
        sum +=x[i];
    printf("%lld\n",sum);
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rrep(i,n) for(ll i = 1; i <= (n); ++i)
#define drep(i,n) for(ll i = (n)-1; i >= 0; --i)
#define all(v) v.begin(),v.end()
#define len(x) (ll)(x).length()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (ll)(x).size()
#define v(T) vector<T>
#define vv(T) vector<vector<T>>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
ll gcd(ll a,ll b){if(a%b==0){return b;}else{return(gcd(b,a%b));}}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
const int INF=1e9;
const ll MX = 1e18;
const ll MOD=INF+7;
const int di[] = {-1,0,1,0};
const int dj[] = {0,-1,0,1};
const double PI=acos(-1);
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
#define YN {puts("YES");}else{puts("NO");}
const ll MAX = 1000001;
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for (ll i = 2; i < MAX; i++){fac[i] = fac[i - 1] * i % MOD;inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;finv[i] = finv[i - 1] * inv[i] % MOD;}}
long long COM(ll n, ll k){if (n < k) return 0;if (n < 0 || k < 0) return 0;return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;}
ll llpow(ll n,ll i){ll cnt=n;  for(ll j=0;j<i-1;j++){n*=cnt;}return n;}

int main() {
    long long n, m; cin >> n >> m;
    string s, t; cin >> s >> t;
    
    long long g = gcd(n, m);
    long long res = n / g * m;
    n /= g, m /= g;
    bool ok = true;
    for (long long i = 0; i < g; ++i) {
        if (s[i*n] != t[i*m]) ok = false;
    }
    if (ok) cout << res << endl;
    else cout << -1 << endl;
}


Measured memory_bytes: 3728
#include <bits/stdc++.h>
using namespace std;
const int INF = 1001001001;

int main() {
int64_t X;
cin >> X;
int a,b;
a = X/500;
X -= 500*a;
b = X/5;
cout << a*1000+ b *5 << endl;


return 0;
}

Measured memory_bytes: 256
import math
n,m = map(int,input().split())

a = input()
list1 = list(map(int,a.split()))
list1.sort()
list1.reverse()
i = 0
s = math.floor(list1[0]/2)

if n == 1:
    print(math.floor(list1[0]/(2**m)))
    exit()

while True:
    while True:
        if i+1 > n:
            break
        if list1[i] < s or m == 0:
            break
        list1[i] = math.floor(list1[i]/2)
        m -= 1
        i += 1
    if m == 0:
        break
    list1.sort()
    list1.reverse()
    s = math.floor(list1[0]/2)
    i = 0
print(sum(list1))

Measured memory_bytes: 15416
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
from collections import deque
import itertools
import heapq
#import bisect
from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint

#oo=list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# ko=list("abcdefghijklmnopqrstuvwxyz")

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def main():
    #l,r,d=map(int,input().split())
    n=int(input())
    a=list(map(int,input().split()))
    totalsum=sum(a)%MOD
    total=0
    temp=0
    for i in range(n):
        temp+=a[i]%MOD
        total+=((totalsum-temp)*a[i])%MOD
    print(total%MOD)



if __name__ == "__main__":

    main()


Measured memory_bytes: 98124
from collections import Counter

def main():
    n, m, k = list(map(int, input().split()))
    friendships = [tuple(map(int, input().split())) for _ in range(m)]
    blockships = [tuple(map(int, input().split())) for _ in range(k)]

    components = list(range(n))
    friends = { }

    for u, v in friendships:
        u -= 1
        v -= 1
        if u not in friends:
            friends[u] = []
        if v not in friends:
            friends[v] = []
        friends[u].append(v)
        friends[v].append(u)

    blocks = { }
    for u, v in blockships:
        u -= 1
        v -= 1
        if u not in blocks:
            blocks[u] = []
        if v not in blocks:
            blocks[v] = []
        blocks[u].append(v)
        blocks[v].append(u)

    # union-find
    cur_comp = 0
    visited = set()

    def bfs(node):
        st = [node]
        comp = node
        while st:
            n = st.pop()
            if n in visited:
                continue
            components[n] = comp
            visited.add(n)
            if n in friends:
                for nbor in friends[n]:
                    st.append(nbor)


    for u in range(n):
        bfs(u)

    hist = Counter(components)
    new_friends = [0] * n

    # for each user, look up component, calculate total
    # size of component, subtract number of users in the block
    # list that are also in that component
    for u in range(n):
        comp = components[u]
        comp_size = hist[comp]
        n_blocked = blocks[u] if u in blocks else set()
        n_friends = friends[u] if u in friends else set()
        n_same_comp = list(filter(lambda v: components[v] == comp, n_blocked))
        # print(u, n_friends, n_blocked, n_same_comp)
        new_friends[u] = comp_size - 1 - len(n_same_comp) - len(n_friends)

    print(' '.join(map(str, new_friends)))


main()


Measured memory_bytes: 94256
#include<stdio.h>
int main(void)
{
	int n,a[200],b[200],c[200];
	int i,j,sum[200];
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d %d %d",&a[i],&b[i],&c[i]);
	}
	for(i=0;i<n-1;i++){
		sum[i]=a[i];
		for(j=i+1;j<n;j++){
			if(sum[i]==a[j]){
				a[i]=0;
				a[j]=0;
			}
		}
		sum[i]=b[i];
		for(j=i+1;j<n;j++){
			if(sum[i]==b[j]){
				b[i]=0;
				b[j]=0;
			}
		}
		sum[i]=c[i];
		for(j=i+1;j<n;j++){
			if(sum[i]==c[j]){
				c[i]=0;
				c[j]=0;
			}
		}
	}
	for(i=0;i<n;i++){
		printf("%d\n",a[i]+b[i]+c[i]);
	}
	return 0;
}


Measured memory_bytes: 2048
//abc135_d.cpp
//Sat Jul 27 20:50:36 2019

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

int main(){
	string s;
	cin >> s;
	ll MOD = 1000000007;
	int slength = s.length();
	ll dp[slength][13];

	fill(dp[0],dp[0]+13,0);
	for (int i=0;i<10;i++){
		int digit;
		if (s[0]=='?'){
			digit = -1;
		}else {
			digit = s[0] - '0';
		}
		if (digit==i || digit == -1){
			dp[0][i] = 1;
		}
	}

	for (int i=1;i<slength;i++){
		fill(dp[i],dp[i]+13,0);
		int digit;
		if (s[i]=='?'){
			digit = -1;
		}else {
			digit = s[i] - '0';
		}
		for (int j=0;j<10;j++){
			if (digit==j || digit==-1){
				for (int k=0;k<13;k++){
					dp[i][(k*10+j)%13] += dp[i-1][k];
				}
			}
		}
		for (int j=0;j<13;j++){
			dp[i][j] = dp[i][j]%MOD;
		}
	}

	cout << dp[slength-1][5] << endl;
//	printf("%.4f\n",ans);
}

Measured memory_bytes: 10624
#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(0); cin.tie(NULL);
typedef long long ll;
using namespace std;


void solve(){
    int l,r,n,cnt=0; cin>>l>>r>>n;
    if(n==1){
        cout<<r-l+1;
        return;
    }
    for(int i=l; i<=r; i++){
        if(i%n==0) cnt++;
    }
    cout<<cnt;
}


int main(){
    fast;
    solve();
}

Measured memory_bytes: 3644
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<ll, int> P;
typedef pair<int, P> E;
#define MOD (1000000007ll)
#define l_ength size
#define EPS (1e-10)

void add_mod(ll &a, ll b){
	a += b;
	a %= MOD;
}

void mul_mod(ll &a, ll b){
	a *= b;
	a %= MOD;
}

vector<P> v;

int main(void){
	int n,i,ans;
	ll a;
	cin >> n;
	for(i=0; i<n; ++i){
		cin >> a;
		v.push_back(P(a,i));
	}
	sort(v.begin(),v.end());
	for(i=0; i<n; i+=2){
		if(v[i].second%2){
			++ans;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 2548
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <set>
using namespace std;
int main(void){
    int a, b;
    cin >> a >> b;
    string ans;
    int good = min(a, b);
    int bad = max(a, b);
    for(int i=0; i<bad; i++){
        cout << good;
    }
    cout << endl;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#define lp(i,n) for(int i=0;i<n;i++)
#include<bits/stdc++.h>


using namespace std;
int main() {
	int a, b;
	cin >> a >> b;
	if (a == b)
		cout << a << endl;
	else if (a < b)
		cout << a << endl;
	else
		cout << a - 1 << endl;
}

Measured memory_bytes: 256
H = []

gets.to_i.times do
  input = gets.split(" ")
  if input[0] == "insert"
    H[input[1].tr("ACGT", "1234").to_i(5)] = 1
  else
    if H[input[1].tr("ACGT", "1234").to_i(5)] == 1
      puts "yes"
    else
      puts "no"
    end
  end
end



Measured memory_bytes: 85088
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include<bits/stdc++.h>
//#include<cstdio>
//#include<algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

int memo[100001];
int to[100001], ne[100001], he[100001];
int dfs(int A) {
	if (memo[A] != -1) return memo[A];
	int saidai = 0;
	for (int i = he[A]; i; i = ne[i]) {
		saidai = max(saidai, dfs(to[i]));
	}
	return memo[A] = saidai + 1;
}

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


	int N, M;
	cin >> N >> M;
	rep1(i, M) {
		int x, y;
		cin >> x >> y;
		to[i] = y;
		ne[i] = he[x];
		he[x] = i;
	}

	rep1(i, N) memo[i] = -1;

	int saidai = 0;
	rep1(i, N) {
		if (memo[i] == -1) saidai = max(saidai, dfs(i) - 1);
	}
	co(saidai);

	Would you please return 0;
}

Measured memory_bytes: 2944
#include <iostream>
#include <vector>
#include <queue>
#include <sstream>
#include <algorithm>
#include <bitset>
#include <limits>
#include <map>
#include <set>
#include <iomanip>
#include <cmath>

using namespace std;

typedef long long int ll;
typedef std::numeric_limits<double> dbl;
const long long int LL_INF=1LL<<60;

vector<string> split(const string& input, char delimiter)
{
    stringstream stream(input);
    
    string field;
    vector<string> result;
    while (getline(stream, field, delimiter)) {
        result.push_back(field);
    }
    return result;
}

//#define DEBUG

ll A, B, M, N, D, K, Q, W, H, T, X, Y;

int main()
{
    cin >> N >> M;
    vector< pair<ll, ll> > students(N), checks(M);
    for (auto& s : students)
        cin >> s.first >> s.second;
    for (auto& c : checks)
        cin >> c.first >> c.second;

    for (auto s : students) {
        ll minimum = INT64_MAX, mIndex;
        for (int i = 0; i < checks.size(); ++i) {
            pair<ll, ll> c = checks[i];
            ll man = abs(s.first - c.first) + abs(s.second - c.second);
            if (minimum > man) {
                minimum = man;
                mIndex = i + 1;
            }
        }
        cout << mIndex << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <cmath>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <vector>

const int mod = 1e9 + 7;
const int kmax = 510000;

long long fact[kmax], fact_inv[kmax], inv[kmax];

void init_comb()
{
    fact[0] = fact[1] = 1;
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < kmax; i++) {
        fact[i] = fact[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % mod;
    }
}

long long comb(int n, int r)
{
    if (n < r) {
        return 0;
    }

    if (n < 0 || r < 0) {
        return 0;
    }

    return fact[n] * (fact_inv[r] * fact_inv[n - r] % mod) % mod;
}

template <typename T, T N>
class UnionFind {
    T parent_[N];
    T rank_[N];
    T size_[N];

public:
    UnionFind();
    T Root(T idx);
    bool IsSame(T x, T y);
    void Unite(T x, T y);
    T GetSize(T idx);
};

template <typename T, T N>
UnionFind<T, N>::UnionFind()
{
    for (T i = 0; i < N; i++) {
        parent_[i] = i;
        rank_[i] = 0;
        size_[i] = 1;
    }
}

template <typename T, T N>
T UnionFind<T, N>::Root(T idx)
{
    return parent_[idx] == idx ? idx : parent_[idx] = Root(parent_[idx]);
}

template <typename T, T N>
bool UnionFind<T, N>::IsSame(T x, T y)
{
    return Root(x) == Root(y);
}

template <typename T, T N>
void UnionFind<T, N>::Unite(T x, T y)
{
    x = Root(x);
    y = Root(y);
    if (x == y) {
        return;
    }

    if (rank_[x] < rank_[y]) {
        parent_[x] = y;
        size_[y] += size_[x];
    } else {
        parent_[y] = x;
        size_[x] += size_[y];
        if (rank_[x] == rank_[y]) {
            rank_[x]++;
        }
    }
}

template <typename T, T N>
T UnionFind<T, N>::GetSize(T idx)
{
    return size_[Root(idx)];
}

long long pow_mod(long long n, long long p, long long m)
{
    if (p == 0) {
        return 1;
    }

    if (p % 2 == 0) {
        long long t = pow_mod(n, p / 2, m);
        return t * t % m;
    }
    return n * pow_mod(n, p - 1, m) % mod;
}

long long nCr_mod(long long n, long long r)
{
    long long x = 1;
    for (long long i = n - r + 1; i <= n; i++) {
        x *= i;
        x %= mod;
    }

    long long a = 1;
    for (long long i = 1; i <= r; i++) {
        a *= i;
        a %= mod;
    }

    long long y = pow_mod(a, mod - 2, mod) % mod;

    return x * y % mod;
}

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;
}

int main()
{
    char c;
    std::cin >> c;

    std::cout << (char)(c + 1) << std::endl;
}


Measured memory_bytes: 256
// C++ program to print connected components in 
// an undirected graph 
#include<iostream> 
#include <list> 
using namespace std; 
int ans = 0;
 int cnt = 0;
// Graph class represents a undirected graph 
// using adjacency list representation 
class Graph 
{ 
	int V; // No. of vertices 

	// Pointer to an array containing adjacency lists 
	list<int> *adj; 

	// A function used by DFS 
	void DFSUtil(int v, bool visited[]); 
public: 
	Graph(int V); // Constructor 
	~Graph(); 
	void addEdge(int v, int w); 
	void connectedComponents(); 
}; 

// Method to print connected components in an 
// undirected graph 
void Graph::connectedComponents() 
{ 
	// Mark all the vertices as not visited 
	bool *visited = new bool[V]; 
	for(int v = 0; v < V; v++) 
		visited[v] = false; 
   
	for (int v=0; v<V; v++) 
	{ 
		if (visited[v] == false) 
		{ 
			// print all reachable vertices 
			// from v 
			DFSUtil(v, visited); 
            ans = max(cnt,ans);
			// cout << "\n"; 
            cnt=0;
		} 
	} 
	delete[] visited; 
} 

void Graph::DFSUtil(int v, bool visited[]) 
{ 
	// Mark the current node as visited and print it 
	visited[v] = true; 
	// cout << v << " ";
    cnt++; 

	// Recur for all the vertices 
	// adjacent to this vertex 
	list<int>::iterator i; 
	for(i = adj[v].begin(); i != adj[v].end(); ++i) 
		if(!visited[*i]) 
			DFSUtil(*i, visited); 
} 

Graph::Graph(int V) 
{ 
	this->V = V; 
	adj = new list<int>[V]; 
} 

Graph::~Graph() 
{ 
	delete[] adj; 
} 

// method to add an undirected edge 
void Graph::addEdge(int v, int w) 
{ 
	adj[v].push_back(w); 
	adj[w].push_back(v); 
} 

// Driver program to test above 
int main() 
{ 
	// Create a graph given in the above diagram 
    int n,m;
    cin>>n>>m;
    Graph g(n);
    for(int i=0; i<m; i++){
        int u,v;
        cin>>u>>v;u--;v--;
        g.addEdge(u, v); 


    }
	 // 5 vertices numbered from 0 to 4 
	

	// cout << "Following are connected components \n"; 
	g.connectedComponents(); 
    cout<<ans<<endl;

	return 0; 
} 


Measured memory_bytes: 29892
def main():
    q, h, s, d = map(int, input().split())
    n = int(input())
    min_1 = min(q*4, h*2, q*2+h, s)
    min_2 = min(min_1*2, d)

    print((n % 2)*min_1 + (n // 2)*min_2)

if __name__ == '__main__':
    main()


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

using namespace std;
using i64 = std::int_fast64_t;
using u64 = std::uint_fast64_t;

class UnionFind {
 public:
  vector<int> parent;

  UnionFind(int n) : parent(n, -1) {}

  int root(int x) {
    if (parent[x] < 0) {
      return x;
    } else {
      return parent[x] = root(parent[x]);
    }
  }

  bool issame(int x, int y) { return root(x) == root(y); }

  int size(int x) { return -parent[root(x)]; }

  bool unite(int x, int y) {
    int rx = root(x), ry = root(y);
    if (rx == ry) return false;
    if (parent[rx] > parent[ry]) swap(rx, ry);
    parent[rx] += parent[ry];
    parent[ry] = rx;
    return true;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, M;
  cin >> N >> M;
  UnionFind uf(N);
  vector<int> A(M), B(M);
  for (int i = 0; i < M; i++) {
    cin >> A[i] >> B[i];
    A[i]--, B[i]--;
  }
  i64 cur = static_cast<i64>(N) * (N - 1) / 2;
  vector<i64> res;
  for (int i = M - 1; i >= 0; i--) {
    res.emplace_back(cur);

    if (uf.issame(A[i], B[i])) continue;
    i64 a = uf.size(A[i]), b = uf.size(B[i]);
    cur -= a * b;
    uf.unite(A[i], B[i]);
  }
  reverse(res.begin(), res.end());
  for (int i = 0; i < (int)res.size(); i++) {
    cout << res[i] << '\n';
  }
  return 0;
}


Measured memory_bytes: 3444
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v.begin(), v.end())
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
 
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; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }
typedef long long ll;
int p[30];
int main()
{
    int n;
    cin >> n;
    REP(i, n)
        cin >> p[i];

    int cnt = 0;
    for (int i = 1; i < n-1; i++)
    {
        if((p[i-1]<p[i] && p[i]<p[i+1]) || (p[i+1]<p[i] && p[i]<p[i-1]) ){
            cnt++;
        }
    }
    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn=1e5+10;
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
int n,m,p,ac[maxn],pen[maxn],acnum,pennum;
string S;

int main()
{
    #ifdef __LOCAL__
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>p>>S;
        if(ac[p]) continue;
        if(S=="WA")
            pen[p]++;
        else if(S=="AC")
            ac[p]=1;
    }
    for(int i=1;i<=n;i++)
    {
        if(ac[i])
        {
            acnum++;
            pennum+=pen[i];
        }            
    }
    cout<<acnum<<" "<<pennum<<endl;
    
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define PI 3.1415926535897
using namespace std;
typedef long long ll;
const int INF = 1000000000;
const ll LINF = 1000000000000000000; //1e18
const double EPS = 1e-10;

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

    ll move = 0;
    ll ans = N - 1;
    ll j;
    for (ll i = 1; i * i <= N; i++)
    {
        if (N % i == 0)
        {
            j = N / i;
            move = i + j - 2;
            ans = min(ans, move);
        }
    }
    cout << ans << "\n";
    return (0);
}

Measured memory_bytes: 256
# ABC133C - Remainder Minimization 2019
def main():
    L, R = list(map(int, input().rstrip().split()))
    MOD = 2019
    if R - L + 1 >= MOD:  # L <= 2019n <= R
        print(0)
    else:  # max: 2018 * 2017 patterns
        L, R = L % MOD, R % MOD
        if L <= 3 and R >= 673:
            print(0)
            return
        ans = float("inf")
        for i in range(L, R):
            for j in range(i + 1, R + 1):
                ans = min(ans, (i * j) % MOD)
        print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;


int N;
vector<double> x, y;
vector<vector<double>> d;


void input() {
    cin >> N;
    x = y = vector<double>(N);
    rep(i, N) cin >> x[i] >> y[i];
}


double dist(double x1, double y1, double x2, double y2) {
    double dx = x1 - x2;
    double dy = y1 - y2;
    double v = sqrt(dx * dx + dy * dy);
    return v;
}


bool judge(double r) {
    rep(i, N-1) {
        for (int j = i+1; j < N; j++) {
            if (d[i][j] > r * 2) continue;
            double mx, my;
            mx = (x[i] + x[j]) / 2;
            my = (y[i] + y[j]) / 2;
            double m = sqrt(r * r - d[i][j] * d[i][j] / 4);
            double x1, y1, x2, y2;
            if (y[i] == y[j]) {
                x1 = x2 = mx;
                y1 = my + m;
                y2 = my - m;
            }
            else {
                double a = -1 * (x[i] - x[j]) / (y[i] - y[j]);
                double dx, dy;
                dx = m * sqrt(1 / (1 + a * a));
                dy = a * dx;
                x1 = mx + dx;
                y1 = my + dy;
                x2 = mx - dx;
                y2 = my - dy;
            }
            bool p = true;
            rep(k, N) {
                if (i == k || j == k) continue;
                if (dist(x[k], y[k], x1, y1) > r) {
                    p = false;
                    break;
                }
            }
            if (p) return true;
            p = true;
            rep(k, N) {
                if (i == k || j == k) continue;
                if (dist(x[k], y[k], x2, y2) > r) {
                    p = false;
                    break;
                }
            }
            if (p) return true;
        }
    }
    return false;
}


int main() {
    input();
    d = vector<vector<double>>(N-1, vector<double>(N));
    rep(i, N-1) {
        for (int j = i+1; j < N; j++) {
            d[i][j] = dist(x[i], y[i], x[j], y[j]);
        }
    }
    double l, r, c;
    l = 0;
    r = dist(0, 0, 1000, 1000);
    while (r - l >= 1e-8) {
        c = (l + r) / 2;
        if (judge(c)) r = c;
        else l = c;
    }
    printf("%.10f", r);
}


Measured memory_bytes: 256
def prepare(n, MOD):

    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


k = int(input())
s = input()
length = len(s)
MOD = 10**9 + 7

fact, inv = prepare(k + length, MOD)

ans = 0

for i in range(length, length + k + 1):
    coef = fact[i - 1] * inv[i - length] * inv[length - 1] % MOD
    ans += coef * pow(25, i - length, MOD) * pow(26, length + k - i, MOD) % MOD

print(ans % MOD)

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



int main(){
        int n, k,max,temp,num,total;
        while(true) {  //ベクターに格納
                cin >> n>>k;
                if(n==0&&k==0){
                  break;
                }
                vector<double> v;
                total=0;
                v.push_back(total);
                for(int i=0;i<n;i++){
                  cin>>num; //入力をnumに代入
                  total+=num;
                  v.push_back(total); //ベクターvにプッシュ
                }

                max=0;
                temp=0;
                for(int i=0; i+k<=n; i++) {
                        temp=v[i+k]-v[i];
                        if(temp>max) max=temp; //tempが最も大きい数値ならmaxを更新
                        temp=0; //tempの初帰化
                }
                cout<<max<<endl;
        }
}


Measured memory_bytes: 3824