akhauriyash/Code-Regression huggingface dataset:
N,M = map(int,input().split())
t = M * 1900 + (N-M) * 100
ac_rate = 1 / (2**M)
rate = 1.0
ans = 0.0
for n in range(1,1000000):
    ans += rate * ac_rate * t * n
    rate *= (1 - ac_rate)
print(round(ans))


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

ll dp[100000+10][3];
int main()
{
	int n;
	cin>>n;
	int arr[n+1][3];
	for(int i=1;i<=n;i++)
	{
		cin>>arr[i][0]>>arr[i][1]>>arr[i][2];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<3;j++)
		{
			if(j-1>=0)
			{
				dp[i][j]=max(dp[i][j],dp[i-1][j-1]+arr[i][j]);
			}
			if(j-2>=0)
			{
			    dp[i][j]=max(dp[i][j],dp[i-1][j-2]+arr[i][j]);
			}
			if(j+2<3)
			{
			    dp[i][j]=max(dp[i][j],dp[i-1][j+2]+arr[i][j]);
			}
			if(j+1<3)
			{
			    dp[i][j]=max(dp[i][j],dp[i-1][j+1]+arr[i][j]);
			}
		}
	}
	cout<<max(dp[n][0],max(dp[n][1],dp[n][2]));
	
}

Measured memory_bytes: 3712
#include <iostream>
#include<algorithm>
#include<set>
#include<queue>
#include<bitset>
#define rep(i,j,n) for(int i=j;i<n;i++)
using namespace std;
#define int long long
struct edge{long long to,cost;};
struct st{int rate,way,num;};
typedef pair<int,int>P;
#define inf 1000000007
string alph("abcdefghijklmnopqrstuvwxyz");
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int d[55][55];
char fi[55][55];int h,w;int sx=0,sy=0,gx,gy;
int bfs(){
    queue <P> que;
    for(int i=0; i<h;i++){
        for(int j=0; j<w;j++){
            d[i][j]=inf;
        }
    }
    que.push(P(sx,sy));
    d[sx][sy]=0;
    while(que.size()){
        P p=que.front();que.pop();
        if(p.first==gx&&p.second==gy)break;
        for(int i=0; i<4;i++){
            int nx=p.first+dx[i],ny=p.second+dy[i];
            if(0<=nx && nx<h && 0<=ny && ny<w && fi[nx][ny]=='.' && d[nx][ny]==inf ){
                que.push(P(nx,ny));
                d[nx][ny]=d[p.first][p.second]+1;
            }
        }
    }
    return d[gx][gy];
}
signed main(){
    cin>>h>>w;
    int count=0;//白の数の総数
    gx=h-1,gy=w-1;
    rep(i,0,h){
        string s;cin>>s;
        rep(j,0,w){
            fi[i][j]=s[j];
        if(fi[i][j]=='.')count++;
        }
    }
    bfs();
    if(d[gx][gy]==inf){
        cout<<-1<<endl;
        return 0;
    }
    cout<<count-d[gx][gy]-1<<endl;
    return 0;
}

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

int n, a, b, p[100], ans;
bool isUsed[100];
int main() {
    cin >> n >> a >> b;
    rep(i, n) cin >> p[i];
    sort(p, p + n);
    int idx2 = lower_bound(p, p + n, a + 1) - p, idx3 = lower_bound(p, p + n, b + 1) - p;
    for (int idx1 = 0; idx1 < n && p[idx1] <= a; idx1++) {
        if (!isUsed[idx1]) {
            isUsed[idx1] = true;
            for (; idx2 < n && p[idx2] <= b; idx2++) {
                if (!isUsed[idx2]) {
                    isUsed[idx2] = true;
                    for (; idx3 < n; idx3++) {
                        if (!isUsed[idx3]) {
                            isUsed[idx3] = true;
                            ans++;
                            goto next;
                        }
                    }
                }
            }
        }
        next:
        ;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
/**** There's three kinds of edges in a di-graph dfs traversal. Like undirected graphs, recursively traversed edges
 * are called tree edges, going to back to an ancestor is known as a back link, going back to an descendent is a down link
 * and going to visited node which is neither an ancestor or a descendent is known as a cross edge.
 * Any back links (which in turn means down links) results in cycles *****/
#include <iostream>
#include <vector>
using namespace std;
vector<int> nodes[100100];
int pre[100100] = {0};
int post[100100] = {0};
int ith = 0;
bool hasCycle(int s)
{
   pre[s] = ++ith;
   for (auto i : nodes[s])
   {
      if (!pre[i])
      {
         if (hasCycle(i))
         {
            return true;
         }
      }
      else if (post[i] == 0)
      {
         return true;
      }
   }
   post[s] = ++ith;
   return false;
}
int main()
{
   int e, n;
   cin >> n >> e;
   for (int i = 0; i < e; ++i)
   {
      int x, y;
      cin >> x >> y;
      nodes[x].push_back(y);
   }
   for (int i = 0; i < n; ++i)
   {
      for (unsigned i = 0; i < n; ++i)
      {
         pre[i] = 0;
         post[i] = 0;
      }
      if (hasCycle(i))
      {
         cout << 1 << "\n";
         break;
      }
      else if (i == n - 1)
      {
         cout << 0 << "\n";
      }
   }
}


Measured memory_bytes: 5520
#include <bits/stdc++.h>
using namespace std;
int ctoi(char c)
{
  if('0'<=c && c<='9') return c-'0';
  else                 return 0;
}

int main()
{
  string S;
  cin >> S;
  int len=S.size();
  int sum=0;
  for(int i=0;i<len;i++)
  {
    sum+=ctoi(S.at(i));
  }

  if(sum%9==0) cout<<"Yes"<<endl;
  else         cout<<"No"<<endl;
}
    

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

int main() {
 

 int N,K;
 cin >> N >> K;

 vector<int> num(10);
 for(int i = 0;i < K;i++) {
   int D;
   cin >> D;
   num.at(D)++;
 }

 for(int i = N;i < 10 * N + 9;i++) {
   int cpy = i;
   bool can = true;
   while(cpy > 0) {
     if(num.at(cpy % 10) != 0) {
       can = false;
     }
     cpy /= 10;
   }

   if(can) {
     cout << i << endl;
     break;
   }
 }


}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <cmath>
#include <cstdio>

using namespace std;

typedef long long ll;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)

int main(int argc, char **argv)
{
    int N;
    cin >> N;
    int W[N];
    REP(i, N) cin >> W[i];

    int S1 = W[0];
    int S2 = 0;
    REP(i, N - 1) S2 += W[i + 1];
    int m = abs(S1 - S2);
    FOR(i, 1, N - 1) {
        S1 += W[i];
        S2 -= W[i];
        if (m > abs(S1 - S2)) m = abs(S1 - S2);
    }
    cout << m << endl;

    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int N = 202020;

inline char get(void) {
    static char buf[100000], *S = buf, *T = buf;
    if (S == T) {
        T = (S = buf) + fread(buf, 1, 100000, stdin);
        if (S == T) return EOF;
    }
    return *S++;
}
template<typename T>
inline void read(T &x) {
    static char c; x = 0; int sgn = 0;
    for (c = get(); c < '0' || c > '9'; c = get()) if (c == '-') sgn = 1;
    for (; c >= '0' && c <= '9'; c = get()) x = x * 10 + c - '0';
    if (sgn) x = -x;
}

int n;
int p[N], q[N];
int f[N], T[N];

inline bool Check(int a, int b, int c) {
    return (a < b && b < c) || (b < c && c < a) || (c < a && a < b);
}

int main() {
    read(n);
    for (int i = 1; i <= n; i++) {
        read(p[i]); q[p[i]] = i;
    }
    for (int i = n - 1; i; i--) {
        if (T[i + 1] == 0) {
            if (q[i] > q[i + 1]) {
                T[i] = 1; f[i] = i + 1;
            }
        } else {
            if (Check(q[f[i + 1]], q[i], q[i + 1])) {
                T[i] = T[i + 1]; f[i] = f[i + 1];
            } else {
                T[i] = T[i + 1] + 1; f[i] = i + 1;
            }
        }
    }
    cout << T[1] << endl;
}

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

int main() {
	int a[100], n;
	cin >> n;
	
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	
	for(int i = n-1; i >= 0; i--){
		cout << a[i];
		if(i != 0){
			cout << " ";
		}else {
			cout << endl;
		}
	}
	return 0;
}


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

using namespace std;

//FILE *fi=freopen("1.txt","r",stdin);

int n,k,q,a[100001];

void nhap()
{
    scanf("%d %d %d",&n,&k,&q);
    for (int i=1;i<=n;++i)
        a[i]=k-q;
    while (q--)
    {
        int x;
        scanf("%d",&x);
        a[x]++;
    }
    for (int i=1;i<=n;++i)
    {
        if (a[i]>0) cout<<"Yes\n";
        else cout<<"No\n";
    }
}

int main()
{
    nhap();
    return 0;
}


Measured memory_bytes: 1024
# -*- coding: utf-8 -*-
import sys

def main():
	R = int(input())	
	if R < 1200:
		print("ABC")
		sys.exit()
	if R < 2800:
		print("ARC")
		sys.exit()
	
	print("AGC")
		
if __name__ == "__main__":
	main()
	

Measured memory_bytes: 2940
#include <stdio.h>

main(){
  int data[10],p[10];
  int i,temp,n,j,max;

  scanf("%d", &n);
  for(i=0;i<n;i++){
    for(j=0;j<10;j++){
      p[j]=0;
    }
    for(j=0;j<10;j++){
      scanf("%d", &data[j]);
    }
    max=-1;
    for(j=0;j<10;j++){
      if(max<data[j]){
	max=data[j];
	p[j]=1;
      }
    }
    max=-1;
    for(j=0;j<10;j++){
      if(p[j]==0){
	if(max<data[j]){
	  max=data[j];
	  p[j]=1;
	}
      }
    }
    temp=0;
    for(j=0;j<10;j++){
      if(p[j]==0){
	temp=1;
      }
    }
    if(temp==0) printf("YES\n");
    else if(temp==1) printf("NO\n");
  }
  return 0;
}

Measured memory_bytes: 0
#include<stdio.h>

int main(){
	int a, b, c;
	scanf("%d %d %d", &a, &b, &c);
	if( a == b && b == c ){
		printf("1\n");
	}else if( a == b || b == c || a == c ){
		printf("2\n");
	}else{
		printf("3\n");
	}
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define ll long long
int main(){
  int N;
  cin>>N;
  string S;
  cin>>S;
  int X[N+1]={};
  rep(i,N){
    if(S[i]=='#') X[i]=1;
    if(i) X[i]+=X[i-1];
  }
  int ans=min(X[N-1],N-X[N-1]);
  rep(i,N) if(i<N-1) ans=min(ans,X[i]+N-1-i-X[N-1]+X[i]);
  cout<<ans<<endl;
}

Measured memory_bytes: 1412
#include <bits/stdc++.h>
using namespace std;
const auto start_time = std::chrono::high_resolution_clock::now();
void timecalculater(){
    #ifndef ONLINE_JUDGE
    auto end_time = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> diff = end_time-start_time;
    cerr<<"Time Taken : "<<diff.count()<<"\n";
    #endif
}
void __print(int x) {cout << x;}
void __print(long x) {cout << x;}
void __print(long long x) {cout << x;}
void __print(unsigned x) {cout << x;}
void __print(unsigned long x) {cout << x;}
void __print(unsigned long long x) {cout << x;}
void __print(float x) {cout << x;}
void __print(double x) {cout << x;}
void __print(long double x) {cout << x;}
void __print(char x) {cout << '\'' << x << '\'';}
void __print(const char *x) {cout << '\"' << x << '\"';}
void __print(const string &x) {cout << '\"' << x << '\"';}
void __print(bool x) {cout << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cout << '{'; __print(x.first); cout << ','; __print(x.second); cout << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? "," : ""), __print(i); cout << "}";}
void _print() {cout << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cout << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define dbg(x...) cout << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif
#define rep(i, n) for(ll i = 0; i < (n); ++i)
#define repA(i, a, n) for(int  i = a; i <= (n); ++i)
#define all(x) x.begin(), x.end()
#define sz(x) (int) (x).size()
#define fill(a) memset(a, 0, sizeof(a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long int> vll;
typedef vector<pii> vii;
ll p=998244353;
const int N=2e5+5;
int main() {
   
    cin.sync_with_stdio(0); cin.tie(0);
    cin.exceptions(cin.failbit);
    int T=1;
    // cin>>T;
    while(T--){
        ll n,m;cin>>n>>m;ll s=0;
        rep(i,m){
        	ll x;cin>>x;s+=x;
        }
        if(n<s){
        	cout<<-1;
        }
        else{
        	cout<<(n-s);
        }
    }   
    timecalculater();
    return 0;   
} 

Measured memory_bytes: 3660
/*
Author: Srinjoy
Language: C++ 17
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define de(a) cout << #a << " = " << a << endl
#define dd(a) cout << #a << " = " << a << " "
#define optimiza_io cin.tie(0); ios_base::sync_with_stdio(0);
#define ZERO(a) memset(a,0,sizeof(a))
#define fileinput(s) freopen(s,"r",stdin)
#define MINUS(a) memset(a,0xff,sizeof(a))
typedef long long ll;
const ll mod = 1000000007;

template<class T>
istream& operator >> (istream& in, vector<T>& v){ for (auto &x : v) { in >> x; } return in; }
 
template<class T>
istream& operator >> (istream& in, pair<T, T> & v){ in >> v.fi >> v.se;return in; }

void printArr(vector<int> arr){
	cout<<"\n------------------------------------\n";

	for(int i=0;i<arr.size();i++) cout<<arr[i]<<" ";
	
	cout<<"\n------------------------------------\n";
}

void printArr(vector<vector<int> > arr){
	cout<<"\n------------------------------------\n";

	for(vector<int> i:arr){
		for(int j:i){
			cout<<j<<" ";
		}
		cout<<endl;
	}
	
	cout<<"\n------------------------------------\n";

}


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

	vector<int> arr(n);
	cin>>arr;

	set<int> arr1;

	for(int i=0;i<n;i++){
		arr1.insert(arr[i]);
	} 

	if(arr1.size() == arr.size()) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	
}

Measured memory_bytes: 10368
#include <iostream>

using namespace std;

int main() {
    int numMulFour = 0;
    int numOdd = 0;
    int numEven = 0;
    int N, a;

    cin >> N;
    for (int n = 0; n < N; n++) {
        cin >> a;
        
        if (a % 4 == 0) { numMulFour++; }
        else if (a % 2 == 0) { numEven++; }
        else { numOdd++; }
    }

    int reqNumMulFour;
    if (numEven != 0) { reqNumMulFour = numOdd; }
    else { reqNumMulFour = numOdd - 1; }

    if (numMulFour >= reqNumMulFour) { cout << "Yes" << endl; }
    else { cout << "No" << endl; }

    return 0;
}


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N,M;
ll K;
ll A[202020],B[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,N) {
		cin>>x;
		A[i+1]=A[i]+x;
	}
	FOR(i,M) {
		cin>>x;
		B[i+1]=B[i]+x;
	}
	
	int ma=0;
	FOR(i,N+1) if(A[i]<=K) {
		x=lower_bound(B,B+M+1,K-A[i]+1)-B-1;
		ma=max(ma,i+x);
	}
	cout<<ma<<endl;
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 6772
#include <bits/stdc++.h>
#define range(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, a) range(i, 0, a)
using namespace std;

int main() {
    int n, t, a;
    cin >> n >> t >> a;
    double mini = 1e9;
    int ans = -1;
    rep (i, n) {
        int h;
        cin >> h;
        if (mini > abs(a - (t - h * 0.006))) {
            mini = abs(a - (t - h * 0.006));
            ans = i;
        }
    }
    cout << ans + 1 << endl;

    return 0;
}

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

int main() {
	string	S;
	cin >> S;
	string	former;
	former = S.substr(0, S.size() / 2);
	int	j;
	j = former.size() - 1;
	for (int i = 0; i < j; i++)
	{
		if (former.at(i) != former.at(j))
		{
			cout << "No" << endl;
			return (0);
		}
		j--;
	}
	if (S.substr((S.size() + 3) / 2 - 1, S.size() / 2) != former)
	{
		cout << "No" << endl;
		return (0);
	}
	cout << "Yes" << endl;
}


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

// i2-i1 = A2+A1
// A1+i1 = -A2+i2

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

  map <int, int> A2_i2;
  vector <int> A(N+1);

  for (int i = 1; i <= N; i++) {
    cin >> A[i];
    A2_i2[-A[i]+i]++;
  }

  long long ans = 0;
  for (int i = 1; i <= N; i++) {
    int A1_i1 = A[i]+i;
    auto it = A2_i2.find(A1_i1);
    if (it != A2_i2.end()) {
      ans += A2_i2[A1_i1];
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 12592
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
int main()
{
    cin.tie(nullptr); ios::sync_with_stdio(false);
    int P, Q, R; cin >> P >> Q >> R;
    cout << min({P+Q, Q+R, R+P}) << '\n';
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,int>P;
typedef pair<int,P>P2;
#define fi first
#define se second
int dx[]={0,1,0,-1};
int dy[]={-1,0,1,0};

signed main(){
  int n,k;
  cin>>n>>k;
  if(n%k)cout<<1<<endl;
  else cout<<0<<endl;
}


Measured memory_bytes: 768
#include <iostream>
#include <array>
#include <algorithm>
#include <map>

//auto print = [](auto x){ std::cout << x; };
auto println = [](auto x){ std::cout << x << std::endl; };
auto read = [](){int x; std::cin >> x; return x;};


int get_rightface_val(std::array<int, 6> &, std::map<int, int> &, int, int);
int get_rightface_idx(int, int);

int main ()
{
  std::array<int, 6> dice;
  std::map<int, int> face_to_idx;

  for (int i=0; i<6; i++)
    {
      dice.at(i) = read();
      face_to_idx[dice.at(i)] = i;
    }

  int q = read();

  for (int i=0; i<q; i++)
    {
      int top = read();
      int front = read();

      int right = get_rightface_val(dice, face_to_idx, top, front);
      println(right);
    }
}

int get_rightface_val(std::array<int, 6> & dice, std::map<int, int> & face_to_idx, int top, int front)
{
  auto itop = face_to_idx[top];
  auto ifront = face_to_idx[front];

  int iright = get_rightface_idx(itop, ifront);

  return dice.at(iright);
}

int get_rightface_idx(int itop, int ifront)
{
  int x;
  if (itop >2)
    x = 5-itop;
  else
    x = itop;

  std::array<int, 4> sides = {(x+1)%3, (x+2)%3, 5-(x+1)%3, 5-(x+2)%3};

  for (int i=0; i<4; i++)
    {
      if (ifront == sides.at(i))
        if (itop > 2)
          return sides.at((i+3) % 4);
        else
          return sides.at((i+1) % 4);
    }
}




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

int main(){
    ll n;
    cin >> n;
    if(n >= 1000) cout << "ABD" << endl;
    else cout << "ABC" << endl;
    return 0;
}

Measured memory_bytes: 3556
#include <iostream>
//#include <fstream>

using namespace std;
//ifstream fin("secv.in");
//ofstream fout("secv.out");

int x, ape[100010], apo[100010], i, n, eMax1, eMax2, oMax1, oMax2, ex1, ex2, ox1, ox2, nr;
int main()
{
    cin >> n;
    nr = n / 2;
    for (i = 1; i <= n; i++) {
        cin >> x;
        if (i % 2 == 0) {
            ape[x]++;
            if (ape[x] > eMax1) {
                if (ex1 != x) {
                    eMax2 = eMax1;
                    ex2 = ex1;
                }
                eMax1 = ape[x];
                ex1 = x;
            } else if (ape[x] > eMax2) {
                eMax2 = ape[x];
                ex2 = x;
            }
        } else {
            apo[x]++;
            if (apo[x] > oMax1) {
                if (ox1 != x) {
                    oMax2 = oMax1;
                    ox2 = ox1;
                }
                oMax1 = apo[x];
                ox1 = x;
            } else if (apo[x] > oMax2) {
                oMax2 = apo[x];
                ox2 = x;
            }
        }
    }
    if (ex1 != ox1)
        cout << (nr - eMax1) + (nr - oMax1);
    else {
        if ((nr - eMax1) + (nr - oMax2) < (nr - eMax2) + (nr - oMax1))
            cout << (nr - eMax1) + (nr - oMax2);
        else
            cout << (nr - eMax2) + (nr - oMax1);
    }
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <climits>
#include <iomanip>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
long long mod = 1000000007;
long long power(long long m,long long n){
    long long res = 1;
    if(n > 0){
        res = power(m,n / 2);
        if(n % 2 == 0){
            res = (res * res) % mod;
        }
        else{
            res = (((res * res) % mod) * m) % mod;
        }
    }
    return res;
}
//modはグローバル変数にしておく
int main(){
  ll n,k;
  cin >> n >> k;
  vector<ll> factorial(3000);
  factorial[0] = 1;
  factorial[1] = 1;
  for(int i = 2;i < 3000;i++)factorial[i] = factorial[i - 1] * i,factorial[i] %= mod;
  for(int i = 1;i <= k;i++){
    ll res = 0;
    res = 1;
    if(n - k + 1 < i)res = 0;
    else{
    res *= factorial[n - k + 1],res %= mod;
    //if(i == 50)cout<<res<<endl;
    res *= power(factorial[i],mod - 2),res %= mod;
      //if(i == 50)cout<<res<<endl;
    res *= power(factorial[n - k + 1 - i],mod - 2),res %= mod;
      //if(i == 50)cout<<res<<endl;
    res *= factorial[k - 1],res %= mod;
      //if(i == 50)cout<<res<<endl;
    res *= power(factorial[i - 1],mod - 2),res %= mod;
      //if(i == 50)cout<<res<<endl;
    res *= power(factorial[k - i],mod - 2),res %= mod;
    }
    cout << res << endl;
  }
  return 0;
}


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

#define rep(i,n) for(long long i = 0; i < (long long)(n); i++)
#define repi(i,a,b) for(long long i = (long long)(a); i < (long long)(b); i++)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define mt make_tuple
#define mp make_pair
template<class T1, class T2> bool chmin(T1 &a, T2 b) { return b < a && (a = b, true); }
template<class T1, class T2> bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

using ll = long long; using vll = vector<ll>; using vvll = vector<vll>; using P = pair<ll, ll>;
using ld = long double;  using vld = vector<ld>; 

int main(void) {
	string s; cin >>s;
	
	if(s[0]==s[1]&&s[1]==s[2]) cout <<"Yes" <<endl;
	else {
		if(s[2]==s[3]&&s[1]==s[2]) cout <<"Yes" <<endl;
		else cout <<"No" <<endl;
	}
	
   return 0;
}

Measured memory_bytes: 256
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <bitset>
#include <functional>
#include <numeric>
#include <ctime>
#include <cassert>
#include <cstring>
#include <fstream>

using namespace std;

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;


int main()
{
    ll n, x;
    cin >> n >> x;
    long long res = n;
    long long a, b;
    if (2 * x < n)
        a = n - x, b = x;
    else if (2 * x > n)
        a = x, b = n - x;
    else
    {
        cout << 3 * x << endl;
        return 0;
    }

    while (b > 0)
    {
        long long syo = a / b, mod = a % b;
        if (mod == 0)
        {
            long long toadd = b*(2 * syo - 1);
            res += toadd;
            break;
        }
        res += b * 2 * syo;
        a = b;
        b = mod;
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(ll i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  ll n, k;
  cin >> n >> k;
  vl a(n);
  rep(i, n) cin >> a[i];
  ll ng = 0, ok = 1e18;
  while(ng + 1 < ok) {
    ll x = (ng + ok) / 2;
    ll now = 0;
    rep(i, n) now += (a[i] + x - 1) / x - 1;
    if(now > k)
      ng = x;
    else
      ok = x;
  }
  cout << ok << endl;
}

Measured memory_bytes: 4836
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> Pii;
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define INF 1000000000
#define rep(i,a,b) for(int i =(a);i<(b);i++)
#define fs first
#define ss second
inline int Scan() {
    int x=0;int f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}

template<typename T, typename U>
static inline void amin(T &x, U y)
{
    if (y < x)
        x = y;
}

// call by reference is used in x
template<typename T, typename U>
static inline void amax(T &x, U y)
{
    if (x < y)
        x = y;
}
//////////////////////////////////////end of template//////////////////////////////////////

vector<int> g[100005];
int main(){
  
   int n;
   cin >> n;
   
   vector<int> in(n+1,0);
   vector<Pii> vp;    
   map<pair<int,int>,int> m; 
    
    
   for(int i =0;i<n-1;i++){
	   int a,b;
	   cin >> a >> b;
	    g[a].pb(b);
	    g[b].pb(a);
	    vp.push_back({a,b});
   }
   
   queue<int> q;
   vector<int> vis(n+1,0);
   vector<int> ctp(n+1,0);
   
   q.push(1);
   vis[1] = 1;
   int k = 0;
   
   while(!q.empty()){
	    
	    int v = q.front();
	    q.pop();
	    if( k < (int)g[v].size()) k = g[v].size();
	    int cur = 1;
	    
	    for(auto ch: g[v]){
			if( vis[ch] ) continue;
		    if( ctp[v] == cur) cur++;
			
			ctp[ch] = cur++;
			m[{v,ch}] = m[{ch,v}] = ctp[ch];
			vis[ch] =1;
			q.push(ch);
		}  
   }
   
      cout << k << endl;
      for(auto i: vp) cout << m[i] << endl;
   
   return 0;    
}




Measured memory_bytes: 20468
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    int n, d, x;    cin >> n >> d >> x;
    vector<int> a(n); 
    for(int i=0; i<n; i++)  cin >> a.at(i);
    for(int i=0; i<n; i++)
        x += 1 + (d-1)/a.at(i);
    cout << x << endl;
}
    

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

#define MIN_INT -2147483648
#define MAX_INT 2147483647
#define MIN_LONG -9223372036854775808L
#define MAX_LONG 9223372036854775807L
#define PI 3.141592653589793238462643383279502884L

#define long long long int

using std::vector;
using std::map;
using std::set;
using std::string;
using std::pair;
using std::cin;
using std::cout;
using std::cerr;

// @author: pashka

int main() {
    std::ios::sync_with_stdio(false);

    int n;
    cin >> n;
    vector<long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    long l = 2;
    long r = 2;
    for (int i = n - 1; i >= 0; i--) {
        long ll = (l + a[i] - 1) / a[i] * a[i];
        long rr = (r / a[i]) * a[i];
        if (rr < ll) {
            cout << "-1\n";
            return 0;
        }
        rr += (a[i] - 1);
        l = ll;
        r = rr;
    }

    cout << l << " " << r << "\n";

    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
using Long = long long;

#define fast ios::sync_with_stdio(0) , cin.tie(0)
#define pb push_back
#define deb(x) cout << "[ " << #x << " = " << x << " ]\n"
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()


const int SZ = 1e5 + 5;

int main(){
   fast;
   string a,b;
   cin >> a >> b;
   bool ok = 1;
   for(int i=0 ; i<a.length(); ++i){
      if(a[i] != b[i] ) ok = 0;
   }
   if(ok) cout << "Yes";
   else cout << "No";
   return 0;
}

Measured memory_bytes: 3656
#include <iostream>
#include <vector>
#include<list>
#include <algorithm>
#include <string>
#include <math.h>
#include<map>
#include <utility>

#include<queue>
using namespace std;
#define REP(i,k,n) for(int i=k;i<n;i++)
 
#define INF (1e10)
typedef long long unsigned int ll;
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
#define MOD 1000000007

template<typename T>
int vector_finder(std::vector<T> vec, T number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}

template<typename T>
T gcd(T a,T b){
	if(b>0){
		return gcd(b, a % b);
	}else{
		return a;
	}
}

template<typename T>
T lcm(T a,T b){
	T g = gcd(a, b);
	return a * b / g;
}

void clear( std::queue<pair<int,int> > &q )
{
   std::queue<pair<int,int> > empty;
   std::swap( q, empty );
}
bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}
template<typename T>
std::vector<T> enum_div(T n)//nの約数を列挙
{
	std::vector<T> ret;
	for(T i=1 ; i*i<=n ; ++i)
	{
		if(n%i == 0)
		{
			ret.push_back(i);
			if(i!=1 && i*i!=n)
			{
				ret.push_back(n/i);
			}
		}
	}
	return ret;
}

int N,M;


int main()
{
  cin>>N;
  ll A[N];
  REP(i,0,N){
    cin>>A[i];
  }

  ll ans = 0;
  REP(i,0,N-1){
    ans += A[i] / 2;
    if(A[i]%2==1&&A[i+1]>0){
      ans++;
      A[i + 1]--;
    }
  }
  ans += A[N - 1] / 2;

  cout<<ans<<endl;

  




  return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define SORT(a) sort((a).begin(), (a).end())
#define RSORT(a) reverse((a).begin(), (a).end())
#define rep(i, n) for (int i = 0; i < n; i++)
#define all(a) ((a).begin(), (a).end())
typedef long long ll;
// const long long INF = 1LL << 60;
const int INF = 1010101010;
// using Graph = vector<vector<int>>;
const int MOD = 1000000007;
int N, M, A[101010], B[101010];
vector<int> Q[101010];

int main() {
  cin >> N >> M;
  rep(i, N) cin >> A[i] >> B[i];
  rep(i, N) Q[A[i]].push_back(B[i]);

  priority_queue<int> que;
  int ans = 0;
  for (int m = 1; m < M + 1; m++) {
    for (auto& b : Q[m]) que.push(b);
    if (!que.empty()) {
      ans += que.top();
      que.pop();
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 6400
N = int(input())

A = list(map(int, input().split()))

counter = [0] * 100001

for a in A:
  if a:
    counter[a-1]+=1
    counter[a]+=1
    counter[a+1]+=1
  else:
    counter[a]+=1
    counter[a+1]+=1

print(max(counter))

Measured memory_bytes: 13964
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5;
void dfs(ll node,vector<vector<ll>>& adj,vector<bool>& vu,set<ll>& s){
  if(vu[node]) return;
  s.insert(node);
  vu[node] = true;
  for(ll i : adj[node]) dfs(i,adj,vu,s);
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll n,x,y;
  cin >> n;
  vector<vector<ll>> adj(2*N);
  for(int i = 0; i < n; ++i){
    cin >> x >> y;
    adj[x-1].push_back(N+y-1);
    adj[N+y-1].push_back(x-1);
  }
  ll ret = -n;
  vector<bool> vu(2*N);
  for(ll i = 0; i < 2*N; ++i){
    set<ll> s;
    dfs(i,adj,vu,s);
    ll nbx = 0,nby = 0;
    for(ll j : s){
      if(j < N) ++nbx;
      else ++nby;
    }
    ret += nbx*nby;
  }
  cout << ret;
  return 0;
}


Measured memory_bytes: 16640
#include <algorithm>
#include <bitset>
#include <cmath>
#include <functional>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <unordered_map>
#include <unordered_set>
using namespace std;

#define ABS(a) (((a) >= 0) ? (a) : -(a))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) > (b) ? (b) : (a))
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define RFOR(i, a, b) for (int i = (a); i >= (b); --i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define POW_10_5 100000
#define POW_10_9 1000000000
#define MOD 1000000007
#define INF (numeric_limits<int>::max()/2)
#define int long long

typedef pair<int, int> Pair;
typedef unordered_map<int, int> Hash;

// ---
int r;

int Ans() {
  return r*r;
}

signed main() {
  cin >> r;

  auto ans = Ans();

  cout << ans << endl;
  return 0;
}


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

int keisan(int num) {
	int ans;
	ans = num*(num - 1) / 2;
	return ans;
}

int main() {
	int N, M;
	int N_ans, M_ans;
	cin >> N >> M;
	N_ans = keisan(N);
	M_ans = keisan(M);

	cout << N_ans + M_ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N=100010;
int a[N],id[N];
inline int gi() {
    int x=0,o=1;
    char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') o=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*o;
}
inline bool cmp(const int &x,const int &y) {return a[x]<a[y];}
int main() {
    int n,A=0,B=0,C=0,D=0;
    long long ans=0;
    cin>>n;
    for(int i=1;i<=n;i++) a[i]=gi(),id[i]=i;
    sort(id+1,id+1+n,cmp);
    for(int i=1;i<=n;i++) a[id[i]]=(i&1);
    for(int i=1;i<=n;i++) {
	if(i&1) {
	    if(a[i]) ++A;
	    else ++B;
	}
	else {
	    if(a[i]) ++C;
	    else ++D;
	}
    }
    for(int i=1;i<=n;i++) {
	if(i&1) {
	    if(A) --A;
	    else --C,--B,++D,++ans;
	}
	else {
	    if(D) --D;
	    else --B,--C,++A,++ans;
	}
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18,MOD = 1e9 + 7;
const int INT_INF = 1e9,INT_MOD=1e9+7;
#define rep(i, N) for(int i = 0; i < N; i++)
typedef pair<int, int> Pi;
typedef pair<double, double> P;
signed main(){
    string s,t;cin>>s>>t;
    cout<<t<<s<<endl;
    return 0;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)

#define DEBUG(x) cout<<#x<<": "<<x<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

#define CHMIN(a, b) a=min((a), (b))
#define CHMAX(a, b) a=min((a), (b))

const int MOD=1000000007;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-11;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, a[114514], b[114514], c[114514];
	cin>>n;
	REP(i, n) cin>>a[i];
	REP(i, n) cin>>b[i];
	REP(i, n) cin>>c[i];
	sort(a, a+n);
	sort(c, c+n);
	ll x, y;
	ll ans=0;
	REP(i, n){
		x=lower_bound(a, a+n, b[i])-&a[0];
		y=&c[n-1]-upper_bound(c, c+n, b[i])+1;
		if(x>0 && y>0) ans+=x*y;
	}
	cout<<ans<<'\n';
	return 0;
}


Measured memory_bytes: 1408
/*
  Warn - Don't change next line else you will get WA verdict. Online Judge is configured to give WA if next line is not present.
  Author - Aryan Choudhary (@aryanc403)
 
  const short DEBUG { 0 };
  #define debug(x) if (DEBUG) cout << #x << " = " << x << '\n'
*/

#pragma warning(disable:4996)
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("-ffloat-store")

#include<iostream>
#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define repA(i,j,n)   for(i=(j);i<=(n);++i)
#define repD(i,j,n)   for(i=(j);i>=(n);--i)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"
#define PI 3.1415926535897932384626433832795
typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;

//const lli [3] ={ 999119999L,1000000007L,1000992299L};
//const lli [3] ={ 97L,101L,103L};
//const lli  = chrono::high_resolution_clock::now().time_since_epoch().count();
clock_t time_p=clock();
void aryanc403()
{
    time_p=clock()-time_p;
    cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
}

class CMP
{
public:
    bool operator()(lli a , lli b) //For min priority_queue .
    {
        return ! ( a <= b );
    }
};

void add( map<lli,lli> &m, lli x,lli cnt=1)
{
    map<lli,lli> ::iterator jt;
    jt=m.find(x);
    if(jt==m.end())         m.insert(mp(x,cnt));
    else                    jt->Y+=cnt;
}

void del( map<lli,lli> &m, lli x,lli cnt=1)
{
    map<lli,lli> ::iterator jt;
    jt=m.find(x);
    if(jt->Y<=cnt)            m.erase(jt);
    else                      jt->Y-=cnt;
}

bool cmp(const ii &a,const ii &b)
{
    return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}
const lli INF = 0xFFFFFFFFFFFFFFFL;
const lli mod = 1000000007L;

    lli T,n,i,j,k,in,cnt,l,r;
    lli m;
    string s;
    vi a;
    vi :: iterator it;
    //priority_queue < lli , vector < lli > , CMP > pq;// min priority_queue .

int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    // freopen("txt.in", "r", stdin);
    // freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
// cin>>T;while(T--)
{

    a.clear();a.reserve(n);
    fo(i,4)
        a.pb(0);
    fo(i,6)
    {
        cin>>in;
        a[in-1]++;
    }
    sort(a.begin(),a.end());
    //for(auto x:a)
      //  cerr<<x<<endl;
    if(a[0]==1&&a[1]==1&&a[2]==2&&a[3]==2)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
    
}   aryanc403();
    return 0;
}

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

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define Debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long LL;
typedef long double LD;
typedef unsigned int uint;
typedef pair <int, int> pii;
typedef unsigned long long uLL;

template <typename T> inline void Read(T &x) {
  char c = getchar();
  bool f = false;
  for (x = 0; !isdigit(c); c = getchar()) {
    if (c == '-') {
      f = true;
    }
  }
  for (; isdigit(c); c = getchar()) {
    x = x * 10 + c - '0';
  }
  if (f) {
    x = -x;
  }
}

template <typename T> inline bool CheckMax(T &a, const T &b) {
  return a < b ? a = b, true : false;
}

template <typename T> inline bool CheckMin(T &a, const T &b) {
  return a > b ? a = b, true : false;
}

const int N = 100005;

int n, a[N];
LL l, r;

int main() {
#ifdef wxh010910
  freopen("d.in", "r", stdin);
#endif
  Read(n);
  for (int i = 1; i <= n; ++i) {
    Read(a[i]);
  }
  l = r = 2;
  for (int i = n; i; --i) {
    LL L = (l + a[i] - 1) / a[i], R = r / a[i];
    if (L > R) {
      puts("-1");
      return 0;
    }
    l = L * a[i], r = (R + 1) * a[i] - 1;
  }
  printf("%lld %lld\n", l, r);
#ifdef wxh010910
  Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#endif
  return 0;
}


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

#include <algorithm>
using namespace std;
struct Fast {
    Fast() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} fast;

long long mod = 1000000007;

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

void yes() {
    cout << "Yes" << endl;
    exit(0);
}
void no() {
    cout << "No" << endl;
    exit(0);
}
#define REP(i, n) for (long long i = 0; i < (n); i++)
vector<long long> dijkstra(vector<vector<pair<long long, long long>>> graph, long long s) {
    vector<long long> ans(graph.size(), -1);
    priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>>
        pq;
    pq.push({0, s});
    while (pq.size() > 0) {
        int cur1 = 0;
        int cur2 = 0;
        if (ans[pq.top().second] != -1) {
            pq.pop();
        } else {
            cur1 = pq.top().first;
            cur2 = pq.top().second;
            pq.pop();
            ans[cur2] = cur1;
            for (long long i = 0; i < graph[cur2].size(); i++) {
                pq.push({cur1 + graph[cur2][i].second, graph[cur2][i].first});
            }
        }
    }
    return ans;
}
vector<vector<pair<long long, long long>>> graph;
signed main() {
    int v, e, r;
    cin >> v >> e >> r;
    vector<long long> as(v);
    graph.resize(v);
    REP(i, e) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back({b, c});
    }
    as = dijkstra(graph, r);
    REP(i, v) {
        if (as[i] == -1) {
            cout << "INF" << endl;
            continue;
        }
        cout << as[i] << endl;
    }
}


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

int main(){
    int S;
    cin >> S;
    int h;
    h = S/3600;
    int A;
    A = S%3600;
    int m;
    m = A/60;
    int s;
    s = A%60;
    cout << h << ":" << m << ":" << s << endl;
    return 0;
}


Measured memory_bytes: 3096
N,C,K = map(int,input().split())
A = []
for n in range(N):
	a = int(input())
	A.append(a)
A.sort()
b = 0
for a in A:
	if b == 0:
		b = 1
		c = 1
		t = a
	elif c >= C:
		b = b + 1
		c = 1
		t = a
	elif a <= t + K and c < C:
		c = c + 1
	elif a > t + K:
		b = b + 1
		c = 1
		t = a
print(b)

Measured memory_bytes: 7388
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int main() {
	ll h,w;
	
	while (true) {
		cin >> h >> w;
		if (h == 0 && w == 0)
			break;

		for (ll i = 0; i < h; i++) {
			for (ll j = 0; j < w; j++) {
				cout << "#";
			}
			cout << endl;
		}
		cout << endl;
	}
		
}



Measured memory_bytes: 3080
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
const int N = 1e6+6;
const ll mod = 1e9+7;
void solve(){
    int n; 
    cin>>n; 
    cout<<n*n*n<<endl;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t=1;
//	cin>>t;
	while(t--)solve();
	return 0;
}


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

int main() {
 
int N,sum=0;
cin >>N;
vector<int> A(N);
for(int i=0; i<N; i++){cin>>A[i];sum+=A[i];}
// vector<vector<int>> A(N,vector<int>(M));
// for(int i=0; i<N; i++){for(int j=0; j<M; j++){cin>>A[i][j];}}
sort(A.begin(),A.end());
for(int i=0;i<N;i++)
{ if(sum%10!=0){cout<<sum<<endl;break;}
 if(A[i]%10!=0)sum-=A[i];

 if(i==N-1)cout<<0<<endl;}
}


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

int main()
{
char a; scanf("%c",&a);
char b;
for(int i=0;i<3;i++){
scanf("%c", &b);
if(a==b){cout<<"Bad"<<endl; return 0;}
else {a=b;}
}
cout<<"Good"<<endl;
return 0;
}

Measured memory_bytes: 256
import sys
from collections import Counter
input = sys.stdin.readline

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a = Counter(a)
    
    other = 0
    
    ans = n
    for k, v in a.items():
        ans -= v - 1
        if not v%2:
            other += 1
    
    ans -= other%2
        

    print(ans)
    
    
    
if __name__ == "__main__":
    main()


Measured memory_bytes: 22116
N, D = map(int,input().split())
dots = []
for i in range(N):
  dot = [int(v) for v in input().split()]
  dots.append(dot)

answer = 0
for i in range(N-1):
  for j in range(i+1,N):
    d1,d2 = (dots[i],dots[j])
    distance = (sum([(v1-v2)**2 for v1,v2 in zip(d1,d2)]))**0.5
    if distance.is_integer():
      answer += 1
print(answer)


Measured memory_bytes: 3064
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <cassert>
#include <numeric>
#include <functional>
//#include <numeric>
#pragma warning(disable:4996) 
 
typedef long long ll;
typedef unsigned long long ull;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF  9223300000000000000
#define LINF2 1223300000000000000
#define LINF3 1000000000000
#define INF 2140000000
const long long MOD = 1000000007;
//const long long MOD = 998244353;

using namespace std;

void vecscl(double c, const double v0[2], double v1[2])
{
    v1[0] = v0[0] * c;
    v1[1] = v0[1] * c;
}

void vecadd(const double v0[2], const double v1[2], double v2[2])
{
    v2[0] = v0[0] + v1[0];
    v2[1] = v0[1] + v1[1];
}

void vecsub(const double v0[2], const double v1[2], double v2[2])
{
    v2[0] = v0[0] - v1[0];
    v2[1] = v0[1] - v1[1];
}

double vecsum(const double v0[2], const double v1[2])
{
    return v0[0] * v1[0] + v0[1] * v1[1];
}

double veclen(const double v[2])
{
    return sqrt(v[0] * v[0] + v[1] * v[1]);
}

bool vecnrm(double eps, const double v0[2], double v1[2])
{
    double len = veclen(v0);
    if (len < eps) {
        return false;
    }
    vecscl(1 / len, v0, v1);
    return true;
}

const double eps = 1e-12;

void solve()
{
    int x0, y0, x1, y1;
    scanf("%d%d%d%d", &x0, &y0, &x1, &y1);
    double p0[2] = { (double)x0, (double)y0 };
    double v0[2] = { (double)x1 - x0, (double)y1 - y0 };
    bool ok = vecnrm(eps, v0, v0);
    assert(ok);

    int Q;
    scanf("%d", &Q);
    int t;
    for (t = 0; t < Q; t++) {
        int x, y;
        scanf("%d%d", &x, &y);
        double v[2] = { (double)x, (double)y };
        double vtmp[2], vtmp2[2], vtmp3[2];
        vecsub(v, p0, vtmp);
        double val = vecsum(v0, vtmp);
        vecscl(val, v0, vtmp2);
        vecadd(p0, vtmp2, vtmp3);
        printf("%.10lf %.10lf\n", vtmp3[0], vtmp3[1]);
    }

    return;
}


int main(int argc, char* argv[])
{
#if 1
    solve();
#else
    int T;
    scanf("%d", &T);
    int t;
    for(t=0; t<T; t++) {
        //printf("Case #%d: ", t+1);
        solve();
    }
#endif
    return 0;
}



Measured memory_bytes: 2760
#include <iostream>
#include <typeinfo>
#include <cstring>
#include <utility>
#include <vector>
#include <bitset>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;


int _gcd2(int l, int s) {
    return s == 0 ? l : _gcd2(s, l % s);
}


int gcd2(int a, int b) {
    return a > b ? _gcd2(a, b) : _gcd2(b, a);
}

int _gcd3(int l, int m, int s) {
    if (s == 0) {
        return gcd2(l, m);
    } else if (m == 0 && s == 0) {
        return l;
    }
    else {
        int r1 = l % s;
        int r2 = m % s;
        return r1 > r2 ? _gcd3(s, r1, r2) : _gcd3(s, r2, r1);
    }
}


int gcd3(int a, int b, int c) {
    if (a >= b && b >= c) {
        return _gcd3(a, b, c);
    } else if (b >= c && c >= a) {
        return _gcd3(b, c, a);
    } else if (c >= a && a >= b) {
        return _gcd3(c, a, b);
    } else if (b >= a && a >= c) {
        return _gcd3(b, a, c);
    } else if (a >= c && c >= b) {
        return _gcd3(a, c, b);
    } else {
        return _gcd3(c, b, a);
    }
}


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

    int ans = 0;
    for (int a = 1; a <= K; a++) {
        for (int b = 1; b <= K; b++) {
            for (int c = 1; c <= K; c++) {
                ans += gcd3(a, b, c);
    }}}

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3628
n,k = map(int,input().split())
ans = 0

for i in range(n):
    if i+1 < k:
        c = 0
        t = i+1
        while t < k:
            t *= 2
            c +=1
        
        ans += (1/n)*(1/2)**c
    
    else:
        ans += (1/n)*(n-i)
        break

print(ans)
        

Measured memory_bytes: 2940
import math

x0,y0,x1,y1 = map(float, raw_input().split())
q = int(raw_input())
for _ in xrange(q):
  x2,y2 = map(float, raw_input().split())
  ax = x1-x0
  ay = y1-y0
  bx = x2-x0
  by = y2-y0
  # check sin is positive or negative
  sin = ax*by-ay*bx
  if sin == 0:
    if(ax*bx < 0 or ay*by < 0):
      print "ONLINE_BACK"
    else:
      if math.fabs(bx) > math.fabs(ax) or math.fabs(by) > math.fabs(ay):
        print "ONLINE_FRONT"
      else:
        print "ON_SEGMENT"
  elif sin > 0:
    print "COUNTER_CLOCKWISE"
  else:
    print "CLOCKWISE"

Measured memory_bytes: 6584
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int a, b, c, d; cin >> a >> b >> c >> d;
    int x = min(b, d) - max(a, c);
    if(x<=0) cout << 0 << endl;
    else cout << x << endl;    
}

Measured memory_bytes: 256