akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
using namespace std;

template <int32_t MOD>
struct mint {
    int64_t value;
    mint() = default;
    mint(int64_t value_) : value(value_) {}
    inline mint<MOD> operator + (mint<MOD> other) const { int64_t c = this->value + other.value; return mint<MOD>(c >= MOD ? c - MOD : c); }
    inline mint<MOD> operator - (mint<MOD> other) const { int64_t c = this->value - other.value; return mint<MOD>(c <    0 ? c + MOD : c); }
    inline mint<MOD> operator * (mint<MOD> other) const { int64_t c = this->value * int64_t(other.value) % MOD; return mint<MOD>(c < 0 ? c + MOD : c); }
    inline mint<MOD> & operator += (mint<MOD> other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; }
    inline mint<MOD> & operator -= (mint<MOD> other) { this->value -= other.value; if (this->value <    0) this->value += MOD; return *this; }
    inline mint<MOD> & operator *= (mint<MOD> other) { this->value = this->value * int64_t(other.value) % MOD; if (this->value < 0) this->value += MOD; return *this; }
};

constexpr int MOD = 1e9 + 7;
mint<MOD> solve(int n, vector<vector<int> > const & g) {
    // cnt[i] is the number of ways to divide the i elements into pairs
    vector<mint<MOD> > cnt(n + 3);
    cnt[0] = 1;
    for (int i = 2; i < cnt.size(); i += 2) {
        cnt[i] = cnt[i - 2] * (i - 1);
    }

    // tree dp
    function<vector<array<mint<MOD>, 2> > (int, int)> go = [&](int i, int parent) {
        vector<array<mint<MOD>, 2> > dp, dp1;
        dp.assign(2, {});
        dp[1][false] = 1;
        for (int j : g[i]) if (j != parent) {
            auto dp2 = go(j, i);
            dp.swap(dp1);
            dp.assign(dp1.size() + dp2.size() - 1, {});
            REP (t, dp1.size()) {
                REP (u, dp2.size()) {
                    REP (p, 2) {
                        REP (q, 2) {
                            dp[t][p ^ q ^ 1] += dp1[t][p] * dp2[u][q] * cnt[u];  // don't use the edge (i, j)
                            dp[t + u][p ^ q] += dp1[t][p] * dp2[u][q];  // use the edge (i, j)
                        }
                    }
                }
            }
        }
        return dp;
    };
    auto dp = go(0, -1);
    assert (dp.size() == n + 1);

    // inclusion exclusion principle
    mint<MOD> acc = 0;
    REP (i, n + 1) {
        acc += dp[i][false] * cnt[i];
        acc -= dp[i][true ] * cnt[i];
    }
    return acc;
}

int main() {
    int n; cin >> n;
    vector<vector<int> > g(n);
    REP (i, n - 1) {
        int x, y; cin >> x >> y;
        -- x; -- y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    cout << solve(n, g).value << endl;
    return 0;
}


Measured memory_bytes: 1664
import math

class abc_163:
    
    def __init__(self):
        pass
    
    def A(self):
        r=int(input())
        print(2*math.pi*r)
    
    def B(self):
        NM=list(map(int,input().split()))
        A=list(map(int,input().split()))
        
        if NM[0]-sum(A)>=0:print(NM[0]-sum(A))
        else:print("-1")
    
    def C(self):
        N=int(input())
        A=list(map(int,input().split()))
        ans_list=[0]*(N+1)
        
        for i in range(N-1):ans_list[A[i]] +=1
        for i in range(1,N+1):print(ans_list[i])
        
    def D(self):
        NK=list(map(int,input().split()))
        
        data_list=[i for i in range(NK[0]+1)]
        reverse_data_list=sorted(data_list, reverse=True)
        
        #累積和格納リスト
        min_sum_data_list=[0]*(NK[0]+1)
        max_sum_data_list=[0]*(NK[0]+1)
        
        #初期値設定
        min_sum_data_list[0]=data_list[0]
        max_sum_data_list[0]=reverse_data_list[0]
        ans_data=0
        
        #累積和の計算
        for i in range(1,NK[0]+1):
            min_sum_data_list[i]+=min_sum_data_list[i-1]+data_list[i] % (pow(10,9)+7)
            max_sum_data_list[i]+=max_sum_data_list[i-1]+reverse_data_list[i] % (pow(10,9)+7)
       
        for i in range(NK[1]-1,NK[0]+1):
            ans_data+=(max_sum_data_list[i]-min_sum_data_list[i]+1) % (pow(10,9)+7)
            
        print(ans_data % (pow(10,9)+7))    
            
    
if __name__=='__main__':
    obj=abc_163()
    obj.D()

Measured memory_bytes: 39884
huge = 10**9+7
n,m = map(int,input().split())
a = [0,1]
b = []
now = 0
for _ in range(m):
  b.append(int(input()))
b.append(n+1)
for i in range(1,n+1):
  if b[now] == i:
    tmp = 0
    now += 1
  else:
    tmp = a[-2] + a[-1]
  a.append(tmp % huge)
print(a[-1])

Measured memory_bytes: 55640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1000000007;
#define INF 1LL<<30
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()


int main(){
    int h,w,a,b;
    cin>>h>>w>>a>>b;
    char ans[h][w];

    rep(i,h){
        rep(j,w){
            if(i<b && j<w-a) ans[i][j]='0';
            else if(i<b && j>=w-a) ans[i][j]='1';
            else if(i>=b && j<w-a) ans[i][j]='1';
            else ans[i][j]='0';
        }
    }

    rep(i,h){
        rep(j,w){
            cout<<ans[i][j];
        }
        cout<<endl;
    }
}

Measured memory_bytes: 4524
#include<bits/stdc++.h>
using namespace std;
#define INF 1e9+5
int dp[100006];
vector<int >v;
int solve(int n)
{
    if(n==0)
        return 0;
    if(n<0)
        return INF;
    if(dp[n]!=-1)
        return dp[n];
    return dp[n]=min(solve(n-1)+abs(v[n]-v[n-1]), solve(n-2)+abs(v[n]-v[n-2]));
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int temp;
        cin>>temp;
        v.push_back(temp);
    }
    memset(dp,-1,sizeof(dp));
    cout<<solve(n-1)<<endl;
    return 0;
}


Measured memory_bytes: 3448
#include <bits/stdc++.h>
#define INF 5000000000000000000
#define ll long long
#define pll pair<ll, ll>
using namespace std;

int main()
{
  ll N;
  cin >> N;
  vector<vector<pll>> say(N);
  for (ll i = 0; i < N; ++i) {
    ll A, x, y;
    cin >> A;
    for (ll j = 0; j < A; ++j) {
      cin >> x >> y;
      say.at(i).push_back({x - 1, y});
    }
  }
  ll ans = 0;
  for (ll i = 0; i < (1 << N); ++i) {
    ll temp = __builtin_popcount(i);
    if (temp < ans) {
      continue;
    }
    bool ok = true;
    for (ll j = 0; j < N; ++j) {
      if (!ok) {
        break;
      }
      if (i & (1 << j)) {
        for (ll k = 0; k < say.at(j).size(); ++k) {
          if (say.at(j).at(k).second == 0) {
            if (((1 << say.at(j).at(k).first) & i)) {
              ok = false;
              break;
            }
          }
          else {
            if (!((1 << say.at(j).at(k).first) & i)) {
              ok = false;
              break;
            }
          }
        }
      }
    }
    if (ok) {
      ans = max(ans, temp);
    }
  }
  cout << ans << "\n";
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int a,b,c,d,e=0;
	scanf("%d %d %d",&a,&b,&c);
	for(d=a;d<=b;d++){
		if(c%d==0){
			e++;
		}
	}
printf("%d\n",e);
return 0;
}

Measured memory_bytes: 596
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func read() string {
	sc.Scan()
	return sc.Text()
}

func rot(x int, y int) (int, int) {
	return -y, x
}

func main() {
	sc.Split(bufio.ScanWords)
	N, _ := strconv.Atoi(read())
	K, _ := strconv.Atoi(read())
	m := make([]int64, K)
	for a := 1; a <= N; a++ {
		m[a%K]++
	}
	var ans int64
	ans = 0
	for a := 0; a < K; a++ {
		if (a+a)%K == 0 {
			b := (K - a) % K
			ans += m[a] * m[b] * m[b]
		}
	}
	fmt.Printf("%d\n", ans)
}


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

const int maxn = 2005;

int n, k, q;
int a[maxn];
set<int> st;

vector<int> solve(vector<int> v) {
	sort(v.begin(), v.end());
	int m = v.size();
	while(v.size() > m - k + 1) {
		v.pop_back();
	}
	if(v.size() < m - k + 1) {
		v.clear();
	}
	return v;
}

int main(int argc, char const *argv[])
{
	// freopen("in", "r", stdin);
	cin >> n >> k >> q;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		st.insert(a[i]);
	}
	int ans = INT_MAX;
	for(int lower : st) {
		std::vector<int> tmp;
		std::vector<int> all;
		for(int i = 1; i <= n + 1; i++) {
			if(a[i] < lower) {
				if(tmp.size()) {
					vector<int> ret = solve(tmp);
					for(int x : ret) {
						all.emplace_back(x);
					}
					tmp.clear();
				}
			} else {
				tmp.emplace_back(a[i]);
			}
		}
		sort(all.begin(), all.end());
		if(all.size() >= q) {
			ans = min(ans, all[q - 1] - lower);
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    int cnt = 0;
    for (int i=0; i<n; i++) {
        int p;
        cin >> p;
        if (p != i+1) {
            cnt++;
        }
    }
    if (cnt < 3) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }

}

Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
#define int ll
const int N=2e5+3;
bool vis[N];
set<int> g[N];
int n,m;
int comp;
void dfs(int node)
{
  vis[node]=1;
  comp++;
  for(auto u:g[node])
  {
    if(vis[u])continue;
    dfs(u);
  }
}
int32_t main()
{
  #ifndef ONLINE_JUDGE
  freopen("in","r",stdin);
  freopen("out","w",stdout);
  #endif
  cin>>n>>m;
  for(int i=0;i<m;i++)
  {
    int u,v;
    cin>>u>>v;u--;v--;
    g[u].insert(v);
    g[v].insert(u);
  }
  int ans=0;
  for(int i=0;i<n;i++)
  {
    if(!vis[i]){comp=0;dfs(i);ans=max(comp,ans);}
  }
  cout<<ans;
 


  
 
}

Measured memory_bytes: 38172
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using vi = vector<int>;
using vb = vector<bool>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
#define FOR(i,a,b) for(ll i = (a); i < (ll)(b); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(obj) (obj).begin(), (obj).end()
#define eb(val) emplace_back(val)
const double PI = acos(-1);
const double EPS = 1e-10;
const ll MOD = 1e9+7;
void cioacc(){//accelerate cin/cout
  cin.tie(0);
  ios::sync_with_stdio(false);
}
signed main(){
  ll n;
  cin >> n;
  vector<pair<ll,pll>> c(n);
  REP(i,n) cin >> c[i].second.first >> c[i].second.second;
  
  REP(i,n) c[i].first = c[i].second.first + c[i].second.second;
  sort(ALL(c));
  ll ans = 0;
  for(ll i=n-1;i>=0;--i){
    if((n-1-i)%2==0) ans += c[i].second.first;
    else ans -= c[i].second.second;
  }
  cout << ans << endl;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n];
    int b[n-1];
    for(int i=0; i<n-1; i++)
        cin>>b[i];
    
    int sum = b[n-2];
    int temp = b[n-2];
    
    for(int i=n-3; i>=0; i--)
    {
        temp = min(temp, b[i]);
        sum += temp;
        temp = b[i];
    }
    sum += temp;
    cout<<sum;
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int MN = 1e5+9;
int N,C,K,t[MN];
int main(){
    scanf("%d%d%d",&N,&C,&K);
    for(int i=1; i<=N; i++)
        scanf("%d", &t[i]);
    sort(t+1,t+N+1);
    int Ans = 0;
    for(int i=1,j=1; i<=N; i=j){
        while(j<=N && j-i<C && t[i]+K>=t[j] ) j++;
        Ans ++;
    }
    printf("%d\n",Ans);
}


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

int a, b, c;

int main() {
    cin >> a >> b >> c;
    int ans = 1e9;
    auto get = [&](int x) {
        if (x > 0 && (x & 1)) return (int)1e8;
        return x < 0 ? -x : x / 2;
    };
    for (int i = -100; i <= 100; i++) {
        ans = min(ans, get(i - a) + get(i - b) + get(i - c));
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
  int N,T,sum; cin >> N >> T;
  sum=0;
  vector<int> vec(N);
  for(int i=0;i<N;i++){
    cin >> vec.at(i);
  }
   for(int i=0;i<N-1;i++){
     if(vec.at(i+1)-vec.at(i)>=T){
       sum=sum+T;
     }
     else{
       sum=sum+vec.at(i+1)-vec.at(i);
     }
   }
  cout << sum+T << endl;
}

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

int main() {
  int A,B;
  string s;
  cin >> A >> B>> s;
  int n = s.size();
  
  int judge=0;
  if (s.at(A)!='-') judge=1;
  
  else {
    s.at(A)='0';
    for (int i=0;i<n;i++) {
      int x = s.at(i)-'0';
      if (0>x || x>9) {
        judge=1;
        break;
      }
    }
  }
  
  if (judge==1) {
    cout << "No";
  }
  else {
    cout << "Yes";
  }
}

Measured memory_bytes: 256
x=int(input())

def log(x,y):
  count=0
  while x>=y:
    x/=y
    count+=1
  return count

M=[-1 for x in range (0,100001)]
M[0]=0
def mini(x):
  if M[x]==-1:
    M[x]=1+min(mini(x-9**log(x,9)),mini(x-6**log(x,6)))
  return M[x]
print(mini(x))


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

int main(){
  ll n; cin >>n;
  string ans = "";
  while(n>0){
    n--;
    ans += (n%26)+'a';
    n /= 26;
  }
  reverse(ans.begin(), ans.end());
  cout << ans << endl;
  return 0; 
}

Measured memory_bytes: 3636
import java.util.stream.DoubleStream;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long k = sc.nextLong();
        long a = n % k;
        long b = k - a;
        System.out.println(a < b ? a : b);
    }
}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
#define fi(a) scanf("%d",&a);
#define fli(a) scanf("%ld",&a);
#define fll(a) scanf("%lld",&a);
#define pi(a) printf("%d\n",a);
#define ppi(i,a) printf("Case %d: %d\n",i,a);
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

int main()
{
    fast
    ll n;
    for(int i=1;i<=5;i++){
        cin >> n;
        if(n==0) cout << i << endl;
    }

    return 0;
}



Measured memory_bytes: 3648
from collections import deque
n,m = map(int,input().split())
data = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    data[a].append(b)
    data[b].append(a)
visited = [0]*n
kind = [-1]*n
dq = deque([])
for i in range(n):
    if not visited[i]:
        dq.append(i)
        while dq:
            p = dq.pop()
            if not visited[p]:
                kind[p] = i
                visited[p] = 1
                for j in data[p]:
                    dq.append(j)
q = int(input())
for _ in range(q):
    a,b = map(int,input().split())
    print("yes" if kind[a]==kind[b] else "no")


Measured memory_bytes: 24772
#include<bits/stdc++.h>
#define ll long long
#define dbg(x) cout<<#x<<": "<<x<<endl;
#define N 3000005
#define M 1000000007
#define pii pair<ll,ll>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;


main()
{
    ll mx=-1e18;
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    mx=max(mx,b*d);
    mx=max(mx,a*c);
    mx=max(mx,a*d);
    mx=max(mx,b*c);
    cout<<mx;
}



Measured memory_bytes: 3632
#include <stdio.h>

int main(){
	int w,n;
	int a[30],b[30],c[30];
	int i,temp=0;
	scanf("%d %d",&w,&n);
	
	for(i=1;i<=w;i++){
		c[i]=i;
	}
		
	
	for(i=0;i<n;i++){
		scanf("%d,%d",&a[i],&b[i]);
		temp=c[a[i]];
		c[a[i]]=c[b[i]];
		c[b[i]]=temp;
	}
	
	for(i=1;i<=w;i++){
		printf("%d\n",c[i]);
	}
	
	return 0;
}
	

Measured memory_bytes: 596
#include <bits/stdc++.h>
using namespace std;
 
/* REPmacro */
#define REP(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define REPR(i,n) for(int i=((int)(n)-1);i>=0;--i)
#define FOR(i,m,n) for(int i=(int)(m);i<(int)(n);++i)
 
/*alias*/
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define MP make_pair 
 
#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
#define next asdnext
#define prev asdprev
#define itn int
 
/*using*/
using ll = long long;
using ull = unsigned long long;
using unsi = unsigned;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using pii = pair<int, int>;
using db = double;
using plex = complex<double>;
using vs = vector<string>;
 
/*template*/
template<class T>inline bool amax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>inline bool amin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
 
/* func */
 
/*struct*/
struct aaa {
	aaa() {
		cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(20);
	};
}aaaaaaa;
 
/* const */
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7; //10^9
const db EPS = 1e-9;
const int dx[] = { 1, 1, 0, -1, -1, -1, 0, 1 }, dy[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
//Counterclockwise from the 9o'clock direction
//Take the x-axis downward and the y-axis right
 
//#define int ll
#define int long long
 
 array<int,200010> a;
signed main()
{
  int n, k;
  cin>>n>>k;
  REP(i,n){//backet law
    int t;cin>>t;
    ++a[t];
  }
  
  sort(&a[0],&a[n+1]);//sort(begin,end)でfirst~lastまでがsortされるから+1
  
  int ans = 0;
  //{0,1,1,2,2,3}の時n-k=変更したい玉の数より6-2なら{0+1+1+2}のように変更されるやつが足される
  for(int i = 0; i <= n-k; ++i)
    ans += a[i];
  
    cout<<ans;
  return 0;
}

Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner src = new Scanner(System.in);


		//a,b,opを入力し、opが？になるまで繰り返す。
		while(true) {
			int a  = src.nextInt();
			String op  = src.next();
			int b  = src.nextInt();

//			opが？なので終了
			if (op.equals("?")) {
				break;
			
//			opが＋、－、＊、/の場合の計算と出力
			}else if(op.equals("+")) {
				System.out.println(a + b);

			}else if(op.equals("-")) {
				System.out.println(a - b);

			}else if(op.equals("*")) {
				System.out.println(a * b);

			}else if(op.equals("/")) {
				System.out.println(a / b);



			}
		}
	}
}



Measured memory_bytes: 26272
n = int(input())
k1 = [None]*(2*n)
for i in range(n):
  a, b = map(int, input().split())
  k1[i] = (a, b, 0)
for j in range(n, 2*n):
  c, d = map(int, input().split())
  k1[j] = (c, d, 1)
k1.sort()
key = []
ans = 0
for i in range(2*n):
  a, b, c = k1[i][0], k1[i][1], k1[i][2]
  if c == 0:
    key.append(b)
    key.sort()
    continue
  for j in range(len(key)-1, -1, -1):
    if key[j] < b:
      ans += 1
      key.remove(key[j])
      break
print(ans)
  
  

Measured memory_bytes: 3064
import java.util.*;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    String s = sc.next();
    
    if(a>=3200){
      System.out.println(s);
    }else{
       System.out.println("red");
    }
  }
}

Measured memory_bytes: 35700
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#define int long long
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 20000;
const int M = 50000;
int n,m,p;
int dis[N];
bool vis[N];
int cnt[N];
int cnte,head[N];
struct edge{
	int to,nxt,w;
}e[M];
void add(int u,int v,int w){
	e[++cnte]=(edge){v, head[u], w};
	head[u]=cnte;
}
namespace h{
	int cnte,head[N];
	edge e[M];
	bool able[N],vis[N];
	void add(int u,int v,int w){
		swap(u, v);
		e[++cnte]=(edge){v, head[u], w};
		head[u]=cnte;
	}
	void bfs(){
		queue<int> q;
		q.push(n);
		able[n]=1;
		vis[n]=1;
		while(!q.empty()){
			int u=q.front();
			q.pop();
			vis[u]=0;
			for(int i=head[u]; i; i=e[i].nxt){
				int v=e[i].to;
				if(!able[v]){
					able[v]=1;
					if(!vis[v]){
						vis[v]=1;
						q.push(v);
					}
				}
			}
		}
	}
}
void spfa(){
	queue <int> q;
	q.push(1);
	cnt[1]++;
	for(int i=1; i<=n; i++){
		dis[i]=-INF;
	}
	vis[1]=1;
	dis[1]=0;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u]; i; i=e[i].nxt){
			int v=e[i].to;
			int w=e[i].w;
			if(h::able[v] && dis[v]<dis[u]+w){
				dis[v]=dis[u]+w;
				if(!vis[v]){
					q.push(v);
					vis[v]=1;
					cnt[v]++;
					if(cnt[v]>n){
						printf("-1\n");
						exit(0);
					}
				}
			}
		}
	}
}
signed main(){
	scanf("%lld%lld%lld",&n,&m,&p);
	for(int i=1; i<=m; i++){
		int u,v,w;
		scanf("%lld%lld%lld",&u,&v,&w);
		w-=p;
		add(u, v, w);
		h::add(u, v, w);
	}
	h::bfs();
	spfa();
	printf("%lld\n",max(0ll, dis[n]));
	return 0;
}


Measured memory_bytes: 640
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		while (n > 0) {
			for (int i = 0; i < n; ++i) {
				int pm = sc.nextInt();
				int pe = sc.nextInt();
				int pj = sc.nextInt();
				if (pm > 99 || pe > 99 || pj > 99) {
					System.out.println("A");
				} else if (pm + pe >= 180) {
					System.out.println("A");
				} else if (pm + pe + pj >= 240) {
					System.out.println("A");
				} else if (pm + pe + pj >= 210) {
					System.out.println("B");
				} else if (pm + pe + pj >= 150 && (pm >= 80 || pe >= 80)) {
					System.out.println("B");
				} else {
					System.out.println("C");
				}
			}
			n = sc.nextInt();
		}
	}
}



Measured memory_bytes: 38296
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}




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

int n,k;
cin >> n >> k;

int ans = 0;

rep(i,n){
    int h; cin >> h;
    if(h >= k) ans++;
}

cout << ans << endl;

return 0;
}

Measured memory_bytes: 256
val mod = 1000000007

fun mul(a: Long, b: Long) = (a * b) % mod

fun inv(n: Long): Long {
    var b = 1
    var v = n
    var ret = 1L
    while (b <= mod - 2) {
        if (b and (mod - 2) != 0) {
            ret = mul(ret, v)
        }
        v = mul(v, v)
        b *= 2
    }
    return ret
}

fun div(a: Long, b: Long) = (a * inv(b)) % mod

fun fac(n: Long) = (1L .. n).fold(1L) { a, b -> mul(a, b) }

fun cmb(n: Long, r: Long) = div(div(fac(n), fac(r)), fac(n - r))

fun main(args: Array<String>) {
    val (x, y) = readLine()!!.split(" ").map { it.toLong() }.let {
        Pair(it[0], it[1])
    }
    println(if ((x + y) % 3 != 0L || x * 2 < y || y * 2 < x) {
        0
    } else {
        cmb((x + y) / 3, (x * 2 - y) / 3)
    })
}


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



int main() {
    long long a,b,c,d;
    cin>>a>>b>>c>>d;

    if((abs(a-b)<=d&&abs(b-c)<=d)||abs(a-c)<=d){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }



}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
bool comp(pair<long long int,long long int>a,pair<long long int,long long int>b)
{
    if(a.first==b.first)
    {
        if(a.second<=b.second)
        return true;
        else
        return false;
    }
    if(a.first>b.first)
    return true;
    else return false;
}
long long int gcd(long long int bdda,long long int chota)
{
    if(chota==0)
        return bdda;
    return gcd(chota,bdda%chota);
}
void solve()
{
    long long int c[1000000]={0};
    long long int m=1;
    long long int s;
    cin>>s;
    while(c[s]==0)
    {
        c[s]=1;
        if(s%2)s=3*s+1;
        else s/=2;
        m++;
    }
    cout<<m;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;    
    t=1;

    //cin>>t;
    while(t--)
    {
        solve();
    }
}


Measured memory_bytes: 11384
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    int a, b, c, d;
    cin >> a;
    cin >> b;
    cin >> c;
    cin >> d;

    int count = 0;
    int tm = 0;
    int start, end;
    for (int i = 0; i <= 101; i++) {
        if (i >= a && i <= b && i >= c && i <= d) {
            if (tm == 0) {
                start = i;
                tm = 1;
            }
        } else {
            if (tm == 1) {
                end = i-1;
                tm = 2;
            }
        }
    }

    if (tm == 2) count = end - start;
    cout << count << endl;
}

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

Measured memory_bytes: 256
def solve():
    n, x = map(int, input().split())
    l = [1]
    nu = [1]
    for i in range(n):
        l.append(l[-1] * 2 + 3)
        nu.append(nu[-1] * 2 + 1)

    def chris(a, b):
        if a == 0:
            return b
        elif b <= a:
            return 0
        hl = l[a]
        if b >= hl - a:
            return nu[a]
        elif hl // 2 + 1 <= b:
            return nu[a - 1] + 1 + chris(a - 1, b - (hl // 2 + 1))
        return chris(a - 1, b - 1)

    print(chris(n, x))


solve()


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

int main(){
	int x,a,b;
	cin >> x >> a >> b;
	int ans = x;
	ans = (x-a)%b;
	if(ans < 0) ans = 0;
	cout << ans << endl;

	return 0;
}




Measured memory_bytes: 256
#include<stdio.h>
#define MAX_N 123456
int prime[MAX_N*2];//index+1????´???°??????0?´???°??§????????????1
main(){
    //?´???°????±???????
    prime[0] = 1;
    for(int i = 2;i*i <= MAX_N*2;i++){
        for(int j = i*2;j <= MAX_N*2;j+=i){
            prime[j-1] = 1;
        }
    }
    int N;
    scanf("%d",&N);
    while(N){
        int count = 0;
        for(int i = N+1;i <= N*2;i++){
            count += !prime[i-1];
        }
        printf("%d\n",count);
        scanf("%d",&N);
    }
}

Measured memory_bytes: 3628
#include<iostream>
#include<math.h>
#include<algorithm>
#define ll long long int
#define FOR(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n)

using namespace std;

int main(){
	int a, b, c;
	cin >> a >> b >> c;
	int t = max(a, max(b, c));
	if(t == a){
		cout << 10*t + b + c << endl;
	}else if(t == b){
		cout << 10*t + a + c << endl;
	}else{
		cout << 10*t + a + b << endl;
	}
	return 0;
}


Measured memory_bytes: 256
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()

cost = [[INF] * (W + 1) for i in range(H + 1)]

field = ["#" * (W + 1)]

for i in range(H):
    line = input()
    field.append("#" + line)

if field[1][1] == "#":
    cost[1][1] = 1
else:
    cost[1][1] = 0

for i in range(1, H + 1):
    for j in range(1, W + 1):
        if i * j == 1:
            continue
        # そのまま
        if field[i][j] == ".":
            cost[i][j] = min(cost[i-1][j], cost[i][j-1])
        else:# 今いるところが黒
            up_cost = cost[i-1][j]
            left_cost = cost[i][j-1]
            # 上が黒
            if field[i-1][j] == ".":
                up_cost += 1
            if field[i][j-1] == ".":
                left_cost += 1
            
            cost[i][j] = min(up_cost, left_cost)
print(cost[H][W])


Measured memory_bytes: 5576
##main#######################################

## INPUT ####################################
arr = list(map(int,list(input().split())))
N=arr[0] #たこ焼き個数
X=arr[1] #max
T=arr[2] #maxの時間(min)

## PROCESSING ###############################

## OUTPUT ###################################
if N % X  > 0 :
	ans=(N // X )+1
else:
	ans=N // X 

print(ans * T)

Measured memory_bytes: 9168
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)

ll mod = 1e09;

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

  string s;
  cin >> s;
  ll ans = 0;
  REP(i, 3){
    if(s[i] == '1') ans++;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
long long i,j,n,m,k;

int main(){
    unsigned long long ans = 100;
    unsigned long long x;
    cin >> x;
    for(i = 1; i < 3761; i++){
        ans += ans/100;
        if(ans>=x){
            cout << i << endl;
            break;
        }
    }
}

Measured memory_bytes: 3628
#include <stdio.h>

int main(void){
  char S[32];
  int i, ans=0,tmp=0;
  scanf("%s",S);
  
  for(i = 0;i<3;i++){ 
    if(S[i-1] == 'R'){
      if(S[i] == 'R'){
        tmp++;
      }
    }else{
      if(S[i] == 'R'){
        tmp=1;
      }
    }
    if(ans<tmp){
      ans=tmp;
    }
  }
  printf("%d",ans);
  return 0;
}

Measured memory_bytes: 2080
n = int(input())
lengths = list(map(int, input().split(' ')))
total = 0
longest = 0
for i in lengths:
  total += i
  if (i > longest):
    longest = i
possible = True
if (total - longest) <= longest:
    possible = False
   
if possible:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3064
#include <stdio.h>

int main(void)
{
	int a, b, c, i, count = 0;

	scanf("%d %d %d", &a, &b, &c);
	b = b;

		for (i = a; i <= b; i++){
			if (c%i == 0) count++;
		}
	
		printf("%d\n", count);

	return 0;
}

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

using namespace std;
typedef long long LL;

#ifdef BTK
#define DEBUG if(1)
#else
#define CIN_ONLY if(1)
struct cww {cww() {CIN_ONLY{ios::sync_with_stdio(false); cin.tie(0);}}
}star;
#define DEBUG if(0)
#endif

#define ALL(v) (v).begin(),(v).end()
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l, T r){bool a = l>r; if (a)l = r; return a;}
template <typename T>inline bool chmax(T &l, T r){bool a = l<r; if (a)l = r; return a;}
template <typename T>istream& operator>>(istream &is, vector<T> &v){for (auto &it : v)is >> it;return is;}

class range {private: struct I { int x; int operator*() { return x; }bool operator!=(I& lhs) { return x<lhs.x; }void operator++() { ++x; } }; I i, n;public:range(int n) :i({ 0 }), n({ n }) {}range(int i, int n) :i({ i }), n({ n }) {}I& begin() { return i; }I& end() { return n; }};

int main() {
	int n;
	cin >> n;
	vector<unsigned> a(n);
	cin >> a;
	sort(ALL(a));
	cout << a.back() << " ";
	int id = 0;
	for (int i : range(1, n-1)) {
		unsigned p = min(a[i], a.back() - a[i]);
		unsigned q = min(a[id], a.back() - a[id]);
		if (p > q)id = i;
	}
	cout << a[id] << endl;
	return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 1012345678;
int N, M, a[114], b[114], c[114], g[19][19], sum[32777], val[32777], dp[19][32777], dp2[32777];
int main() {
	cin >> N >> M;
	int all_cost = 0;
	for (int i = 0; i < M; i++) {
		cin >> a[i] >> b[i] >> c[i]; a[i]--, b[i]--;
		sum[(1 << a[i]) + (1 << b[i])] += c[i];
		g[a[i]][b[i]] = g[b[i]][a[i]] = c[i];
		all_cost += c[i];
	}
	for (int i = 0; i < M; i++) {
		for (int j = i + 1; j < M; j++) {
			if (c[i] < c[j]) {
				swap(a[i], a[j]);
				swap(b[i], b[j]);
				swap(c[i], c[j]);
			}
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 1 << N; j++) {
			dp[i][j] = -inf;
		}
	}
	dp[0][1] = 0;
	for (int i = 3; i < 1 << N; i += 2) {
		for (int j = 0; j < N; j++) {
			if (i & (1 << j)) {
				int sb = i - (1 << j);
				for (int k = 0; k < N; k++) {
					if ((sb & (1 << k)) && g[j][k] != 0) {
						dp[j][i] = max(dp[j][i], dp[k][sb] + g[j][k]);
					}
				}
			}
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 1 << N; j++) {
			if (!(j & (1 << i))) {
				sum[j + (1 << i)] += sum[j];
			}
		}
	}
	int ret = 0;
	for (int i = 0; i < 1 << N; i++) {
		if ((i & 1) && (i & (1 << (N - 1)))) {
			int sb = (1 << N) - i - 1;
			for (int j = sb; j >= 0; j--) {
				j &= sb;
				val[j] = 0;
				for (int k = 0; k < N; k++) {
					if (i & (1 << k)) {
						val[j] = max(val[j], sum[j + (1 << k)]);
					}
				}
			}
			dp2[0] = 0;
			for (int j = sb; j >= 0; j--) {
				j &= sb;
				if (j == sb) continue;
				int rj = sb - j;
				dp2[rj] = 0;
				for (int k = rj; k > 0; k = (k - 1) & rj) {
					dp2[rj] = max(dp2[rj], dp2[rj - k] + val[k]);
				}
			}
			ret = max(ret, dp2[sb] + dp[N - 1][i]);
		}
	}
	cout << all_cost - ret << endl;
	return 0;
}

Measured memory_bytes: 2432
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stdio.h>
int compare(const void *a,const void *b){
    if(*(long long *)a>*(long long *)b)return 1;
    return -1;
}
int main(int argc, const char * argv[]) {
    long long n;
    scanf("%lld",&n);
    if(n>=30)
        printf("Yes");else printf("No");
    return 0;
}


Measured memory_bytes: 1736
Sa=input()
Sb=input()
Sc=input()

turn="A"

while True:
    if turn=="A":
        if Sa=="":
            print("A")
            break
    
        elif Sa[0]=="a":
            turn="A"
            Sa=Sa[1::]
        elif Sa[0]=="b":
            turn="B"
            Sa=Sa[1::]
        elif Sa[0]=="c":
            turn="C"
            Sa=Sa[1::]
    elif turn=="B":
        if Sb=="":
            print("B")
            break
    
        elif Sb[0]=="a":
            turn="A"
            Sb=Sb[1::]
        elif Sb[0]=="b":
            turn="B"
            Sb=Sb[1::]
        elif Sb[0]=="c":
            turn="C"
            Sb=Sb[1::]
    elif turn=="C":
        if Sc=="":
            print("C")
            break
    
        elif Sc[0]=="a":
            turn="A"
            Sc=Sc[1::]
        elif Sc[0]=="b":
            turn="B"
            Sc=Sc[1::]
        elif Sc[0]=="c":
            turn="C"
            Sc=Sc[1::]
    
    


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define st first
#define nd second

using ll = long long;
using namespace std;
using pii = pair<int, int>;
const int N = 4e3 + 10;
int qs[N][3], a[N];
char s[N];
int main(){
	int n;
	scanf("%d%s", &n, s + 1);
	if(n < 3){
		return !printf("0");
	}
	for(int i = 1;i <= n; i++){
		if(s[i] == 'R') a[i] = 0;
		else if(s[i] == 'G') a[i] = 1;
		else a[i] = 2;
	}
	for(int i = 1; i <=n; i++){
		for(int j = 0; j < 3; j++){
			qs[i][j] += qs[i-1][j];
		}
		qs[i][a[i]]++;
	}
	ll ans = 0;
	for(int i = 2; i < n; i++){
		for(int j = i - 1; j > 0; j--){
			if(a[i] == a[j]) continue;
			int k = 3 - a[i] - a[j];
			ans  += qs[n][k] - qs[i][k];
			if(2 * i - j <= n && a[2 * i - j] == k) ans--;		
		}
	}
	printf("%lld", ans);

}

Measured memory_bytes: 3824
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<long long> vll;
typedef vector<pair<int,int>> vp;
typedef pair<int,int> pii;
#define INF (int)(1e9)
#define MAXX 1.1529215e+18
#define inf 999999
#define EPS (1e-7)
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define REP(i,n) for(int i=1;i<=(int)(n);i++)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define ALL(a)  a.begin(),a.end()
#define RALL(a) a.begin(),a.end(),greater<int>()
#define ROT(a) a.begin(),a.begin()+1,a.end()
#define RROT(a) a.begin(),a.end()-1,a.end()
#define PB push_back
#define MP make_pair
#define PI acos(-1.0)
#define sz(a) a.size()
const ll MOD = 1e9+7;
const int MAX = 10000000;
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
//cout << 'H' << endl;
//next_permutation(ALL(p));
//typedef priority_que<int> pque;//これは大きい順
//typedef priority_que<int, vector<int>, greater<int>> pque;//これは小さい順


int main(){
	int a,b,c;
	cin >> a >> b >> c;
	if(a+b+c < 22){
		cout << "win" <<endl;
	}else{
		cout << "bust" << endl;
	}


  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int a,b,c,d;
	scanf("%d %d %d %d",&a,&b,&c,&d);

    for(;;){
		c-=b;
		if(c <= 0){
			printf("Yes\n");
			break;
        }
		a-=d;
		if(a <= 0){
			printf("No\n");
			break;
        }
	}
	return 0;
}


Measured memory_bytes: 1660
N = int(input())
a = list(map(int, input().split()))
# N = 4
# a = [1, -3, 1, 0]
# N = 5
# a = [3, -6, 4, -5, 7]
# N =6
# a = [-1, 4, 3, 2, -5, 4]


def solve(start):
    cum_sum = 0
    cost = 0
    for i in range(N):
        cum_sum += a[i]
        if i % 2 == start:
            if cum_sum < 1:
                cost += 1 - cum_sum
                cum_sum = 1
        else:
            if cum_sum > -1:
                cost += (cum_sum + 1)
                cum_sum = -1
    return cost


ans = min(solve(start=0), solve(start=1))
print(ans)


Measured memory_bytes: 14212
#include<iostream>
#include<iomanip>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int main(){
  int h,w;
  cin>>h>>w;
  vector<string> sl = vector<string>(h);
  for(int i=0;i<h;i++){
    cin>>sl[i];
  }

  vector<vector<vector<int>>> cnt = vector<vector<vector<int>>>(2010, vector<vector<int>>(2010, vector<int>(2, 0)));  // vvvi[30][20][10]

  for(int hi=0;hi<h;hi++){
    int wi = 0;
    while(wi<w){
      if(sl[hi][wi]=='.'){
        int c = 0;
        int wj = wi;
        while(wj<w && sl[hi][wj]=='.'){
          c += 1;
          wj += 1;
        }
        for(int j=wi;j<wj;j++){
          cnt[hi][j][0] = c;
        }
        wi = wj;
      }else{
        wi += 1;
      }
    }
  }

  for(int wi=0;wi<w;wi++){
    int hi = 0;
    while(hi<h){
      if(sl[hi][wi]=='.'){
        int c = 0;
        int hj = hi;
        while(hj<h && sl[hj][wi]=='.'){
          c += 1;
          hj += 1;
        }
        for(int j=hi;j<hj;j++){
          cnt[j][wi][1] = c;
        }
        hi = hj;
      }else{
        hi += 1;
      }
    }
  }

  int res = -1;
  for(int hi=0;hi<h;hi++){
    for(int wi=0;wi<w;wi++){
      if(sl[hi][wi]=='.'){
        int r = cnt[hi][wi][0]+cnt[hi][wi][1];
        if(r>res){
          res = r;
        }
      }
    }
  }
  cout<<res-1<<endl;
  return 0;
}


Measured memory_bytes: 227456
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  
  int N, K, sum = 0;
  cin >> N >> K;
  
  for ( int i = 0; i < N; i++ ) {
    int ball;
    cin >> ball;
    
    if ( K > ball ) {
      
      if ( K/2 < ball )
        sum += ( K - ball ) * 2;
      else
        sum += ball * 2;
    
    }else
      sum += ( ball - K ) * 2;

  }
  
  cout << sum << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<map>
#include<algorithm>
#include<set>
#include<list>

using namespace std;

typedef struct {
    int sum;
    int a;
    int b;
} sab;

bool cmp(const sab& a, const sab& b)
{
    return a.sum > b.sum;
}

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

    vector<sab> ab(n);
    for (int i = 0; i < n; i++) {
        sab tmp;
        cin >> tmp.a >> tmp.b;
        tmp.sum = tmp.a + tmp.b;
        ab[i] = tmp;
    }

    sort(ab.begin(), ab.end(), cmp);

    long long count = 0;
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) {
            count += ab[i].a;
        } else {
            count -= ab[i].b;
        }
    }

    cout << count << endl;

    return 0;
}


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

const double EPS = 1e-10;
double add(double a, double b) {
    if(abs(a+b) < EPS*(abs(a)+abs(b))) return 0;
    return a+b;
}
struct Vector {
    double x, y;
    Vector() {}
    Vector(double x, double y):x(x), y(y) {}
    Vector operator+(Vector v) {return Vector(add(x, v.x), add(y, v.y));}
    Vector operator-(Vector v) {return Vector(add(x, -v.x), add(y, -v.y));}
    Vector operator*(double d) {return Vector(x*d, y*d);}
    Vector operator/(double d) {return Vector(x/d, y/d);}
    double dot(Vector v) {return add(x*v.x, y*v.y);}
    double cross(Vector v) {return add(x*v.y, -y*v.x);}
};
istream &operator>>(istream &is, Vector &v) {return is >> v.x >> v.y;}
ostream &operator<<(ostream &os, const Vector &v) {return os << v.x << ' ' << v.y;}
double sqdist(Vector &v, const Vector &u) {return (v-u).dot(v-u);}
//線分v2-v1上にあるか
bool on_seg(Vector &v1,Vector &v2, const Vector &p) {
    return (v1-p).cross(v2-p) == 0 && (v1-p).dot(v2-p) <= 0;
}
//v1-v2とu1-u2の交点
Vector intersection(Vector &v1,Vector &v2,Vector &u1,Vector &u2) {
    assert((v1-v2).cross(u1-u2)); //2直線が平行だとだめ
    return v1 + (v2-v1)*((u2-u1).cross(u1-v1)/(u2-u1).cross(u2-v1));
}
//p2-p1へのQの投影
Vector projection(Vector &p1,Vector &p2,Vector &Q) {
    return p1+(p2-p1)*(Q-p1).dot(p2-p1)/sqdist(p1, p2);
}
//p1-p2を軸としたQの線対称移動
Vector reflection(Vector &p1,Vector &p2,Vector &Q) {
    return projection(p1, p2, Q)*2-Q;
}
bool cmp_x(const Vector &v, const Vector &u) {
    if(v.x != u.x) return v.x < u.x;
    return v.y < u.y;
}
//頂点数nの頂点集合vv
vector<Vector> convex_hull(vector<Vector> &vv, int n) {
    sort(vv.begin(), vv.end(), cmp_x);
    int k = 0;
    vector<Vector> res(n*2);
    for(int i = 0; i < n; i++) {
        while(k > 1 && (res[k-1]-res[k-2]).cross(vv[i]-res[k-1]) <= 0) k--;
        res[k++] = vv[i];
    }
    for(int i = n-2, t = k; i >= 0; i--) {
        while(k > t && (res[k-1]-res[k-2]).cross(vv[i]-res[k-1]) <= 0) k--;
        res[k++] = vv[i];
    }
    res.resize(k-1);
    return res;
}

signed main() {
    Vector p0, p1, p2, p3;
    int q;
    cin >> q;
    while(q--) {
        cin >> p0 >> p1 >> p2 >> p3;
        if((p0-p1).dot(p2-p3) == 0) {
            cout << 1 << endl;
        } else if((p0-p1).cross(p2-p3) == 0) {
            cout << 2 << endl;
        } else {
            cout << 0 << endl;
        }
    }

}


Measured memory_bytes: 3228
#ifndef BZ
#ifndef __clang__
#pragma GCC optimize "-O3"
#endif
#endif
#include <bits/stdc++.h>

#define FASTIO
#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

#ifdef FASTIO
#define scanf abacaba
#define printf abacaba
#endif

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;


/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/

const ll MOD = 1e9 + 7;

ll n, k;
ll a[210];

int getmin(ll l, ll r) {
	if (l == r)
		return __builtin_popcountll(l);
	int ans = 0;
	for (int x = 60; x >= 0; --x) {
		if ((l >> x) != (r >> x)) {
			ans += 1;
			break;
		}
		else {
			ans += (l >> x) & 1;
		}
	}
	return min(ans, __builtin_popcountll(l));
}

map<vector<ll>, vector<pair<ll, ll> > > mm;
ll b[210];

int main() {
#ifdef FASTIO
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#endif
	cin >> n >> k;
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	sort(a, a + n);
	for (int x = 0; x <= 60; ++x) {
		vector<ll> vv;
		for (int i = 0; i < n; ++i)
			vv.push_back(a[i] % (1ll << x));
		vv.push_back((1ll << x) - 1);
		sort(ALL(vv));
		vv.resize(unique(ALL(vv)) - vv.begin());
		ll lst = 0;
		for (ll r: vv) {
			ll l = lst;
			int cnt = getmin(l, r);
			if (cnt + x > k || r > a[0])
				continue;
			for (int i = 0; i < n; ++i)
				b[i] = (a[i] - r) >> x;
			vector<ll> vv;
			for (int i = 1; i < n; ++i)
				vv.push_back(b[i] - b[0]);
			mm[vv].emplace_back(max(0ll, b[0] - (k - cnt - x)), b[0] + 1);
			lst = r + 1;
		}
	}
	ll ans = 0;
	for (auto x: mm) {
		auto &vv = x.second;
		sort(vv.begin(), vv.end());
		if (vv.empty())
			continue;
		ll cur = vv[0].first;
		for (auto p: vv) {
			if (p.first <= cur) {
				if (p.second > cur)
					ans += p.second - cur, cur = p.second;
			}
			else {
				ans += p.second - p.first;
				cur = p.second;
			}
		}
	}
	cout << ans % MOD << "\n";
	return 0;
}




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

int main(){

  int n;
  cin>>n;
  
  vector<string> data(n);
  

  
  for (int i=0;i<n;i++){
    cin>>data.at(i);
  }
  
  
    sort(data.begin(),data.end());
  
   
  int count=1;
  
  for (int i=1;i<n;i++){
    
    int check=1;  


    if (data.at(i)==data.at(i-1)){
      check=0;
    }
    
    count+=check;
  }
  
  cout<<count<<endl;

  return 0;
}
  













Measured memory_bytes: 9544
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100005, MOD = 1000000007;

ll N, arr[MAXN], ps[MAXN];

ll pkt(ll a, ll b) {
	if (b == 0) return 1;
	else if (b&1) return a*pkt(a, b-1)%MOD;
	else {
		ll tmp = pkt(a, b/2);
		return tmp*tmp%MOD;
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}
	
	ll nFact = 1;
	for (int i = 1; i <= N; i++) nFact = (nFact*i)%MOD;
	ps[0] = 0;
	for (int i = 1; i <= N; i++) {
		ps[i] = (ps[i-1] + nFact*pkt(i, MOD-2))%MOD;
	}
	
	ll ans = 0;
	for (int i = 1; i <= N; i++) {
		ans = (ans + arr[i]*(ps[i] + ps[N+1-i] - ps[1]))%MOD;
		if (ans < 0) ans += MOD;
	}
	cout << ans << "\n";
	
	return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
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; }
template<typename T>
vector<T> table(int n, T v) { return vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
    auto val = table(args...);
    return vector<decltype(val)>(n, move(val));
}
const ll INF = 1e9;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
double a,b,c,d;
double f(double x){
    return a*x*x*x+b*x*x+c*x+d;
}
void solve(double a,double b,double c,double d){
    int plus = 0,minus = 0;
    double D = b*b-3*a*c;
    if (D >= 0){
        double al = (-b+sqrt(D))/3.0/a;
        double be = (-b-sqrt(D))/3.0/a;
        if (al > be) swap(al,be);
        if (a > 0){
            if (f(al) >= 0 && 0 >= f(be)){
                if (0 < al) plus++;
                else if (be < 0) minus++;
                else{
                    if (d > 0) plus++;
                    else if (d < 0) minus++;
                }
            } 
            if (f(al) >= 0){
                if (al < 0) minus++;
                else{
                    if (d > 0) minus++;
                    else if (d < 0) plus++;
                }
            }
            if (f(be) <= 0){
                if (be > 0) plus++;
                else{
                    if (d > 0) minus++;
                    else if (d < 0) plus++;
                }
            }
        }
        else{
            if (f(al) <= 0 && 0 <= f(be)){
                if (0 < al) plus++;
                else if (be < 0) minus++;
                else{
                    if (d > 0) minus++;
                    else if (d < 0) plus++;
                }
            }
            if (f(al) <= 0){
                if (al < 0) minus++;
                else{
                    if (d > 0) plus++;
                    else if (d < 0) minus++;
                }
            }
            if (f(be) >= 0){
                if (be > 0) plus++;
                else{
                    if (d > 0) plus++;
                    else if (d < 0) minus++;
                }
            }
        }
    }else{
        if (a > 0){
            if (d > 0) minus++;
            else if (d < 0) plus++;
        }
        else{
            if (d > 0) plus++;
            else if (d < 0) minus++;
        }
    }
    PRINT(plus << " " << minus);
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    rep(i,n){
        cin >> a >> b >> c >> d;
        solve(a,b,c,d);
    }
}


Measured memory_bytes: 3272
a = [int(_) for _ in input().split()]
if all(1 <= item <= 100 for item in a):
    print('Possible' if 0 == a[0] % 3 or 0 == a[1] % 3 or 0 == (a[0]+a[1]) % 3 else 'Impossible')
else:
    print('hoge!')

Measured memory_bytes: 2940