akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <map>
#include <utility>
#include <stdlib.h>
#define llint long long
#define mod 998244353

using namespace std;
typedef pair<llint, llint> P;

llint modpow(llint a, llint n)
{
	if(n == 0) return 1;
	if(n % 2){
		return ((a%mod) * (modpow(a, n-1)%mod)) % mod;
	}
	else{
		return modpow((a*a)%mod, n/2) % mod;
	}
}

llint n, m;
map<P, llint> mp;
llint dp[100005][2];

int main(void)
{
	cin >> n >> m;
	llint a, b, c;
	for(int i = 0; i < m; i++){
		cin >> a >> b >> c;
		mp[make_pair(a, b)] = c;
	}
	
	if(n == 2){
		llint sum = 0;
		for(int i = 1; i <= 2; i++){
			for(int j = 1; j <= 2; j++){
				if(mp.count(make_pair(i, j))) sum ^= mp[make_pair(i, j)];
			}
		}
		if(m == 4) cout << 1-sum << endl;
		else cout << (1<<(3-m)) << endl;
		return 0;
	}
	
	llint x = 0, px = 0;
	for(auto it = mp.begin(); it != mp.end(); it++){
		P p = it->first;
		if(abs(p.first - p.second) <= 2) continue;
		x++;
		P q = make_pair(p.second, p.first);
		if(mp.count(q)){
			px++;
			if(mp[p] != mp[q]){
				cout << 0 << endl;
				return 0;
			}
		}
	}
	x -= px/2;
	
	dp[1][0] = dp[1][1] = 1;
	if(mp.count(make_pair(1, 1))){
		dp[1][1-mp[make_pair(1, 1)]] = 0;
	}
	for(int i = 1; i < n; i++){
		for(int j = 0; j < 2; j++){
			int cnt = 0, sum = j;
			if(mp.count(make_pair(i, i+1))) cnt++, sum ^= mp[make_pair(i, i+1)];
			if(mp.count(make_pair(i+1, i))) cnt++, sum ^= mp[make_pair(i+1, i)];
			for(int k = 0; k < 2; k++){
				if(mp.count(make_pair(i+1, i+1)) && mp[make_pair(i+1, i+1)] != k) continue;
				if(cnt == 2 && sum != k) continue;
				int cnt2 = 0, sum2 = 0;
				if(i >= 2){
					if(mp.count(make_pair(i+1, i-1))) cnt2++, sum2 ^= mp[make_pair(i+1, i-1)];
					if(mp.count(make_pair(i-1, i+1))) cnt2++, sum2 ^= mp[make_pair(i-1, i+1)];
					if(cnt2 == 2 && sum2 != j) continue;
				}
				else cnt2 = 2;
				
				llint tmp = 1;
				if(cnt < 2) tmp *= (1<<(1-cnt));
				if(cnt2 < 2) tmp *= (1<<(1-cnt2));
				dp[i+1][k] += dp[i][j] * tmp; dp[i+1][k] %= mod;
			}
		}
	}
	llint ans = (dp[n][0] + dp[n][1]) % mod;
	
	llint l = n - 3;
	llint cnt = l*(l+1)/2 - x;
	ans *= modpow(2, cnt), ans %= mod;
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 4992
n = int(input())
A = []
for i in range(n):
    A.append(int(input()))

# list G
m = 0
G = []
G.append(int(1))

while True:
  m += 1
  x = G[m-1]*3 + 1
  if x <= n and m < 100:
      G.append(x)
  else:
      break
G.reverse()

def iSort(A,n,g,cnt):
    for i in range(g,n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j = j - g
            cnt += 1
        A[j+g] = v
    return cnt

def sSort(A,n,G,m):
    cnt = 0
    for i in range(m):
        cnt = iSort(A,n,G[i],cnt)
    return cnt

print(m)
print(*G)
print(sSort(A,n,G,m))
for i in range(n):
    print(A[i])


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

int main(){
  int h,w;
  bool can = true;
  cin >> h >> w;
  vector<vector<char>> map(h, vector<char>(w));
  
  for(int i=0; i<h; i++){
    for(int j=0; j<w; j++){
      cin >> map[i][j];
    }
  }
  
  const int dx[4] = {-1,0,0,1};
  const int dy[4] = {0,-1,1,0};
  
  for(int i=0; i<h; i++){
    for(int j=0; j<w; j++){
      if(map[i][j] == '.') continue;
      
      int count = 0;
      for(int d=0; d<4; d++){
        const int ni = i+dy[d];
        const int nj = j+dx[d];
        
        if(ni<0 || ni >=h) continue;
        if(nj<0 || nj >=w) continue;
        if(map[ni][nj] == '#') count++;
      }
      if(count == 0){
        can = false;
        break;
      }
    }
    if(can == false) break;
  }
  
  if(can == true){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
      
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define scanVec(vec , n) for(int i = 0; i < n ; i++){ cin>>vec[i];}
#define printVec(vec , n) for(int i = 0; i < n ; i++){ cout<<vec[i]<<" ";}
#define S second
#define F first
const int  MOD = 1e9 + 7;
const int  N = 1e5 + 7;
int dp[N];
bool vis[N];
vector<int> g[N];

void dfs(int u){
	vis[u] = true;
	if(! g[u].size()){
		dp[u] = 0;
		return;
	}

	for(int i = 0 ; i < g[u].size(); i++){
        int v = g[u][i];
		if(!vis[v]) dfs(v);
		dp[u] = max(dp[u],1 + dp[v]);
	}
}


//  a d f j k  l  ;
int main(){
    ios::sync_with_stdio(0);  cin.tie(0);
    int n , m , u , v;
    cin>>n>>m;
    for(int i = 0 ; i < m ; i++){
        cin>>u>>v;
        g[u].pb(v);
    }

    for(int i = 1;i <= n; i++){
		if(!vis[i]) dfs(i);
	}
	
	int mx = 0;
	for(int i = 1;i <= n; i++) mx = max(mx, dp[i]);
	cout << mx << endl;




    return 0;
}

Measured memory_bytes: 8320
#!/usr/bin/env python3
import sys


def solve(H: int, A: int):
    result = 0
    while H > 0:
        H = H - A
        result += 1
    print(result)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    solve(H, A)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <string>

using namespace std;

#define LL long long

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

LL md = 1000000007;

LL power2(int n) {
	LL res = 1;
	LL mul = 2;
	while (n > 0) {
		if (n % 2) {
			res *= mul;
			res %= md;
		}
		mul *= mul;
		mul %= md;
		n /= 2;
	}
	return res;
}

int main() {
	int n;
	LL *a;
	cin >> n;
	a = new LL[n];
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	sort(a, a + n);
	LL res = 0;
	for (int i = 0; i < n; ++i) {
		res += (a[i] * (LL)(n + 1 - i));
		res %= md;
	}
	res %= md;
	res *= power2(2 * n - 2);
	res %= md;
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define TOP 0 
#define BOTTOM 1
#define FRONT 2
#define BACK 3
#define RIGHT 4
#define LEFT 5

void north(int dice[]){
	int to[6];
	to[BACK] = dice[TOP];
	to[BOTTOM] = dice[BACK];
	to[FRONT] = dice[BOTTOM];
	to[TOP] = dice[FRONT];

	to[LEFT] = dice[LEFT];
	to[RIGHT] = dice[RIGHT];

	rep(i,6)dice[i] = to[i];

}

void right(int dice[]){
	int to[6];
	to[FRONT] = dice[LEFT];
	to[LEFT] = dice[BACK];
	to[BACK] = dice[RIGHT];
	to[RIGHT] = dice[FRONT];
	
	to[BOTTOM] = dice[BOTTOM];
	to[TOP] = dice[TOP];
	
	rep(i,6)dice[i] = to[i];
}

void east(int dice[]){
	int to[6];
	to[TOP] = dice[LEFT];
	to[LEFT] = dice[BOTTOM];
	to[BOTTOM] = dice[RIGHT];
	to[RIGHT] = dice[TOP];
	
	to[FRONT] = dice[FRONT];
	to[BACK] = dice[BACK];
	
	rep(i,6)dice[i] = to[i];
}


int main(){
	string s;
	int n;
	
	while(cin >> n ,n){
		int ret = 1;
		int dice[6] = {1,6,2,5,3,4};
		
		rep(i,n){
			cin >> s;
			switch(s[0]){
			case 'N':
				north(dice);
				break;
			case 'S':
				rep(i,3)north(dice);
				break;
			case 'R':
				rep(i,3)right(dice);
				break;
			case 'L':
				right(dice);
				break;
			case 'E':
				east(dice);
				break;
			case 'W':
				rep(i,3)east(dice);
				break;
			}
			ret += dice[0];
		}
		cout << ret << endl;
	}
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
 int main ()
 {
   int N, A;
   cin >> N >> A;
   N = N % 500;
   if (N <= A) {
     cout << "Yes" << endl;
   }
   else {
     cout << "No" << endl;
   }
 }
   
     

Measured memory_bytes: 256
n, m= gets.split.map(&:to_i)

ar = n.times.map{gets.split.map(&:to_i)}
tot = 0

ar.sort_by{|a, b|a}.each do |a, b|
  if b < m
    tot += a * b
    m -= b
  else
    tot += a * m
    break
  end
end

puts tot

Measured memory_bytes: 12664
import java.util.*;

public class Main{
    public  static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int count = 0;
        while(a<=b){
            if(c % a == 0){
                count++;
            }
        a++;
        }
    System.out.println(count);
    }
}


Measured memory_bytes: 26200
#include <cstdio>
#include <algorithm>
typedef long long LL;
typedef unsigned long long ULL;
const int MAXN = 100005;
const int P = 1000000007;
const double eps = 1e-6;
using namespace std;
inline int getint() {
    int r = 0; bool b = true; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') b = false; c = getchar(); }
    while (c >= '0' && c <= '9') { r = (r<<1)+(r<<3) + c - '0'; c = getchar(); }
    return b ? r : -r;
}
LL calc(LL x) { return x * x * x; }
int main() {
    int n,k;
    n=getint();k=getint();
    if (k&1) printf("%lld\n", calc(n / k));
    else printf("%lld\n", calc(n / k) + calc((n + k / 2) / k));
}


Measured memory_bytes: 128
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] ai = new int[n];
        for(int i=0; i<n; i++) {
            ai[i] = in.nextInt();
        }
        int ans = 0;
        for(int i=0; i<n; i++) {
            if(i%2==0 && ai[i]%2==1) {
                ans++;
            }
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 35692
#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>;
using V = vector<int>;

int main(int argc, char const *argv[])
{
    int n, k; cin >> n >> k;
    V p(n); rep(i,n) cin >> p[i];
    int s = 0; rep(i,k) s += p[i]; //0からk-1まで
    int mx = s;

    for (int i = 0; i < n-k; i++)
    {
        s += - p[i] + p[i + k];
        mx = max(mx, s);

    }
  	double ans = (mx + k);
  	ans /= 2;
    printf("%.10f\n", ans);
    return 0;
}


Measured memory_bytes: 1024
// 勝手に変えてごめん！

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;
 
public class Main
{
 
  static Integer[] x = new Integer[114514];
  static boolean used[] = new boolean[114514];
 
  public static void main(String[] args) throws IOException
  {
    BufferedReader r = new BufferedReader(new InputStreamReader(System.in), 1);
    String s = r.readLine();
    String[] sl = s.split("[\\s]+");
 
    int n = Integer.parseInt(sl[0]);
    int m = Integer.parseInt(sl[1]);
 
    HashMap<Integer, HashMap<Integer, Integer>> map = new HashMap<Integer, HashMap<Integer, Integer>>();
 
    for(int i = 0; i <= n; i++)
    {
      map.put(i, new HashMap<Integer, Integer>());
    }
 
    for(int i = 0; i < m; i++)
    {
      s = r.readLine();
      sl = s.split("[\\s]+");
      int left = Integer.parseInt(sl[0]);
      int right = Integer.parseInt(sl[1]);
      int dist = Integer.parseInt(sl[2]);
 
      HashMap<Integer, Integer> h = map.get(left);
      h.put(right, dist);
      h = map.get(right);
      h.put(left, - dist);
    }
 
    for(int i = 1; i <= n; i++)
    {
      x[i] = null;
    }
 
    for(int v = 1; v <= n; v++)
    {
      if(used[v]) continue;
      x[v] = 0;
      sub(map, v);
    }
 
 	/*
    for(int i = 1; i <= n; i++)
    {
      HashMap<Integer, Integer> h = map.get(i);
      for(Entry<Integer, Integer> e : h.entrySet())
      {
        if(x[e.getKey()] != x[i] + e.getValue())
        {
          System.out.println("No");
          System.exit(0);
        }
      }
    }
    */
 
    System.out.println("Yes");
 
  }
 
  public static void sub(HashMap<Integer, HashMap<Integer, Integer>> map, int i)
  {
    if(used[i]) return;
    used[i] = true;
    HashMap<Integer, Integer> h = map.get(i);
    for(Entry<Integer, Integer> e : h.entrySet())
    {
      if(x[e.getKey()] == null)
      {
        x[e.getKey()] = x[i] + e.getValue();
      	sub(map, e.getKey());
      }
      else
      {
        if(x[e.getKey()] != x[i] + e.getValue())
        {
          System.out.println("No");
          System.exit(0);
        }
      }
    }
  }
}

Measured memory_bytes: 208284
import Data.Bits
import Data.Foldable (foldlM,foldrM)
import Data.Maybe (fromJust)
import Data.List
import qualified Data.Vector.Unboxed.Mutable as V
import Control.Monad
import qualified Data.ByteString.Lazy.Char8 as B
import Debug.Trace

solve :: [(Int,Int)] -> Int -> Int -> Int
solve [] l r = r - l + 1
solve ((l,r):ls) maxl minr = solve ls (max maxl l) (min minr r)

main :: IO ()
main = do
  [n,m] <- map read.words <$> getLine :: IO [Int]
  list <- replicateM m $ do
    [l,r] <- map read.words <$> getLine :: IO [Int]
    return (l,r)
  print $ max 0 $ solve list 0 100000


Measured memory_bytes: 56700
#include <iostream>
#include <stdio.h>
#include <string>
#include <sstream>
#include <vector>
#include <stdlib.h>
#include <math.h>
#include <list>
#include <algorithm>

using namespace std;

int main(void){
	//FILE* fp_in = freopen("data.txt", "r", stdin);

	int a,b;
	while( scanf("%d%d",&a,&b) != -1 ) {
		stringstream s;
		s << (a+b);
		cout << s.str().length() << endl;
	}

	//while(1){}
	return 0;
}

Measured memory_bytes: 1232
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

struct FastIO{
  FastIO(){
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
}fastio_beet;


template <typename T>
vector<T> dijkstra(Int s,vector<vector<pair<Int, T> > > & G){
  const T INF = numeric_limits<T>::max();
  using P = pair<T, Int>;
  Int n=G.size();
  vector<T> d(n,INF);
  vector<Int> b(n,-1);
  priority_queue<P,vector<P>,greater<P> > q;
  d[s]=0;
  q.emplace(d[s],s);
  while(!q.empty()){
    P p=q.top();q.pop();
    Int v=p.second;
    if(d[v]<p.first) continue;
    for(auto& e:G[v]){
      Int u=e.first;
      T c=e.second;
      if(d[u]>d[v]+c){
        d[u]=d[v]+c;
        b[u]=v;
        q.emplace(d[u],u);
      }
    }
  }
  return d;
}

//INSERT ABOVE HERE
signed main(){
  Int n,m,k;
  cin>>n>>m>>k;
  vector<Int> ps(n),cs(n),js(n);
  for(Int i=0;i<n;i++) cin>>ps[i];
  for(Int i=0;i<n;i++) cin>>cs[i],cs[i]--;
  for(Int i=0;i<n;i++) cin>>js[i];

  using P = pair<Int, Int>;
  vector< vector<P> > G(n+1);
  for(Int i=0;i<m;i++){
    Int u,v,t;
    cin>>u>>v>>t;
    u--;v--;
    G[u].emplace_back(v,t);
    G[v].emplace_back(u,t);
  }

  auto ds=dijkstra(0,G);

  const Int OFS = 2e9;
  for(Int i=0;i<n;i++)
    G[n].emplace_back(i,ds[i]-ps[i]+OFS);

  auto dt=dijkstra(n,G);
  const Int INF = 1e18;
  vector<Int> ans(k,-INF);
  for(Int i=0;i<n;i++)
    chmax(ans[cs[i]],js[i]-(dt[i]-OFS+ds[i]));

  for(Int x:ans) cout<<x<<"\n";
  cout<<flush;
  return 0;
}



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

int64_t power(int64_t x, int64_t y){
  if(y < 0)
    return 0;
  else{
    int64_t n = 1ll;
    for(int64_t i = 0; i < y; i++)
      n *= x;
    return n;
  }
}

int64_t digit(int64_t x, int64_t y, int64_t n){
  return x%power(n,y+1)/power(n,y);
}

int main(){
    int n; cin >> n;
    vector<int> p(n);
    rep(i,n) cin >> p[i];
    vector<int> q(n);
    rep(i,n) cin >> q[i];
    int ans = 0;
    if(p > q) swap(p,q);
    while(p < q){
        next_permutation(p.begin(),p.end());
        ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;


class MinSumAbs {
  std::multiset<ll> l, r;
  ll lsum, rsum;
public:
  MinSumAbs():lsum(0),rsum(0){}
  void add(ll a){
    l.insert(a); lsum += a;
    if(l.size()-r.size()>1){
      auto itr = --l.end();
      ll x = *itr;
      l.erase(itr); lsum -= x;
      r.insert(x); rsum += x;
    }
    if(r.size() != 0){
      auto itrl = --l.end();
      auto itrr = r.begin();
      ll x = *itrl, y = *itrr;
      if(x > y){
        l.erase(itrl); lsum -= x;
        r.erase(itrr); rsum -= y;
        l.insert(y); lsum += y;
        r.insert(x); rsum += x;
      }
    }
  }
  std::pair<ll,ll> get() {
    if(l.empty()) return std::make_pair(0, 0);
    auto itr = --l.end();
    ll x = *itr;
    ll N = l.size();
    ll M = r.size();
    return std::make_pair(x, N * x - lsum + rsum - M * x);
  }
};


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

  ll bsum = 0;
  MinSumAbs msa;
  rep(i,Q){
    int x;
    cin >> x;
    if(x == 1){
      ll a, b;
      cin >> a >> b;

      bsum += b;
      msa.add(a);
    }else{
      pair<ll,ll> res = msa.get();
      cout << res.first << " " << res.second + bsum << endl;
    }
  }
    
  return 0;
}



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

int main() {
  int n, c, k;
  cin >> n >> c >> k;
  vector<int> t(n);
  for (int i = 0; i < n; i++) {
    cin >> t.at(i);
  }
  sort(t.begin(), t.end());
  int bus = 0;
  for (int i = 0; i < n;) {
    ++bus;
    int starti = i;
    while (i < n && t.at(i) - t.at(starti) <= k && i - starti < c) ++i;
  }
  cout << bus << endl;
}

Measured memory_bytes: 3768
#include<stdio.h>
#include<stdlib.h>
 
struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL
 
Node root;
 
 
Node treeMinimum(Node x){
  while(x->left!=NIL){
    x = x->left;
  }
  return x;
 
}
 
Node treeMaximum(Node x){
  while(x->right!=NIL){
    x = x->right;
  }
  return x;
 
}
 
Node treeSearch(Node u, int k){
  if(u==NIL || k==u->key) return u;
 
  if(k < u->key) return treeSearch(u->left, k);
  else return treeSearch(u->right, k);
}
 
Node treeSuccessor(Node x){
  Node y;
 
  if(x->right != NIL) return treeMinimum(x->right);
 
  y = x->parent;
  while(y!=NIL && x == y->right){
    x = y;
    y = y->parent;
  }
  return y;
}
 
void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y
 
  if(z->left == NIL || z->right == NIL) y = z;
  else y = treeSuccessor(z);
 
  if(y->left!=NIL) x = y->left;
  else x = y->right;
 
  if(x!=NIL) x->parent = y->parent;
 
  if(y->parent == NIL) root = x;
  else if(y == y->parent->left) y->parent->left = x;
  else y->parent->right = x;
 
  if(y!=z) z->key = y->key;
 
 
}
 
void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;
 
  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;
 
  while(x!=NIL){
    y = x;
    if(z->key < x->key) x = x->left;
    else x = x->right;
  }
    z->parent = y;
 
    if(y==NIL) root = z;
    else if(z->key < y->key) y->left = z;
    else y->right = z;
   
 
 
}
 
void inorder(Node u){
  if(u!=NIL){
  inorder(u->left);
  printf(" %d",u->key);  
  inorder(u->right);
  }
  else return;
}
void preorder(Node u){
  if(u!=NIL){
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
  }
  else return;
}
 
 
int main(){
  int n,i, x;
  char com[20];
  scanf("%d", &n);
 
  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }
 
  return 0;
}

Measured memory_bytes: 19360
lines = STDIN.read.split("\n")
lines.each do |line|
  h, w = line.split(" ").map(&:to_i)
  break if h == 0 && w == 0
  h.times do |i|
    w.times do |j|
      if (i + j) % 2 == 0
        print "#"
      else
        print "."
      end
    end
    print "\n"
  end
  print "\n"
end

Measured memory_bytes: 8716
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,x;
ll ans;
int main() {
	//freopen("1.txt","r",stdin);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) {
		scanf("%d",&x);
		ans+=x-1;
	}
	printf("%lld\n",ans);
	return 0;
}

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

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    int ans = min(min(min(abs(a - b) + abs(b - c),
            abs(a - c) + abs(c - b)),
            min(abs(b - a) + abs(a - c),
            abs(b - c) + abs(c - a))),
            min(abs(c - a) + abs(a - b),
            abs(c - b) + abs(b - a)));

    cout << ans << endl;
}

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

typedef unsigned long long ll;

ll bp, ba, N, A, B;

int main()
{
    cin >> N >> A >> B;
    bp = N / (A + B);
    N = N % (A + B);
    if(N >= A) ba = A;
    else ba = N;

    cout << bp * A + ba << endl;
}

Measured memory_bytes: 256
using System;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int tarou = 0, hanako = 0;

            for (int i = 0; i < n; i++)
            {
                string input = Console.ReadLine();
                string[] judge = input.Split(' ');

                int decision = judge[0].CompareTo(judge[1]);//0??\????????£??????1????????????????????§??????
                if (decision == 0)
                {
                    tarou += 1;
                    hanako += 1;
                }
                else if (decision > 0)
                {
                    tarou = tarou + 3;
                }
                else
                {
                    hanako = hanako + 3;
                }
            }

            Console.WriteLine(string.Format("{0} {1}", tarou, hanako));
            
        }
    }
}

Measured memory_bytes: 9908
fn main(){
  proconio::input!{n:usize,mut a:[u128;n]};
  let mut ans = 1;
  a.sort();
  for i in a{
    ans*=i;
    if(10 as u128).pow(18)<ans{
      println!("{}",-1);
      return
    }
  }
  println!("{}",ans)
}

Measured memory_bytes: 6132
#include<bits/stdc++.h>
using namespace std;
#define  inf 2e18
#define  mod 1000000007
#define  bg begin()
#define  en end()
#define  ll long long int
#define  pb push_back
#define  mp make_pair
#define  vi vector<int>
#define  vll vector<long long int>
#define  vpll vector<pair<long long int,long long int> >
#define  vpii vector<pair<int,int> >
#define  vstr vector<string>
#define  mpii map<int ,int>
#define  mpll map<long long int,long long int >
#define  max3(a,b,c) max(a,max(b,c))
#define  min3(a,b,c) min(a,min(b,c))
#define  w(t) ll t; cin>>t; while(t--)
#define  vin(v,n) for(int i=0;i<n;i++){cin>>x; v.pb(x);  }
#define  for0(i,n) for(int i=0;i<n;i++)
#define  for1(i,n) for(int i=1;i<=n;i++)
#define  forv(it,v) for(auto it=v.begin();it!=v.end();it++)
#define  mem(a,val) memset(a,val,sizeof(a))
#define  Sort(vec) sort(vec.begin(),vec.end())
#define  RSort(vec) sort(vec.rbegin(),vec.rend())
#define  eb emplace_back
#define  bs binary_search
#define  lb(v,a) lower_bound(v.begin(),v.end(),a)
#define  ub(v,a) upper_bound(v.begin(),v.end(),a)
#define  deb1(x) cerr<<#x<<": "<<x<<" "<<endl
#define  deb2(x, y) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define  deb3(x, y, z) cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define  deb4(a, b, c, dp) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#dp<<": "<<dp<<endl
#define  FIFO ios::sync_with_stdio(false); cin.tie(0);cout.tie(0)
#define  yes "YES"
#define  no "NO"
#define  PI 3.141592653589793238462643383279502884L
ll Ceil(ll a, ll b) {return a / b + (a % b != 0);}
ll fastModExp(ll a, ll b) { ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
// 2- Dimensional vector:- vector<vector<int> > v(n, vector<int> (26, 0));

mpll mpx;

int main() {

ll a,b;
cin>>a>>b;
cout<<a*b<<endl;

    return 0;
}

Measured memory_bytes: 3624
# https://atcoder.jp/contests/abc122/tasks/abc122_c

N, Q = [int(x) for x in input().split()]
S = input().strip()
m = [0] * N
for i in range(1, N):
    if S[i-1:i+1] == 'AC':
        m[i] = m[i-1] + 1
    else:
        m[i] = m[i-1]

for i in range(Q):
    l, r = [int(x) for x in input().split()]
    print(m[r - 1] - m[l - 1])


Measured memory_bytes: 6140
import Numeric
stddev ns =
  sqrt $ ((sum [(s-m)^2 | s <- ns]) / n)
  where m = sum ns / n
        n = fromIntegral $ length ns

main = do
  n <- readLn :: IO Int
  if n == 0 then return ()
  else do
    putStrLn =<< fmap (show . stddev . (map read . words)) getLine
    main

Measured memory_bytes: 4908
#include<iostream>

using namespace std;

int main(){

  int n;
  cin>>n;
  bool flag = false;
  while(n>0){
  if(n%10==7){
  flag = true;
  break;}
  n/=10;
  }
  
  if(flag)
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
    
return 0;}

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

X_min = N / 1.08
X_max = (N+1) / 1.08

if abs(int(X_min) - X_min) == 0.0:
    print(int(X_min))
else:
    a = int(X_min) + 1 
    if a < X_max:
        print(a)
    else:
        print(":(")


Measured memory_bytes: 2940
/*Function Template*/
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pint;
const int MAX = 510000;
const int MOD = 1000000007;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define Rep(i, n) for(ll i = 1; i < (n); i++)
#define ALL(a)  (a).begin(),(a).end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll fac[MAX], finv[MAX], inv[MAX];


template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }

}
ll Len(ll n) {
  ll s=0;
  while(n!=0) s++, n/=10;
  return s;
}


ll Sint(ll n) {
  ll m=0,s=0,a=n;
  while(a!=0) s++, a/=10;
  for(ll i=s-1;i>=0;i--) m+=n/((ll)pow(10,i))-(n/((ll)pow(10,i+1)))*10;
  return m;
}


ll Svec(vector<ll> v){
  ll n=0;
  for(ll i=0;i<v.size();i++) n+=v[i];
  return n;
}


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


ll Factorial(ll n){
  ll m=1;
  while(n>=1) m*=n,n--;
  return m;
}

void runlength(string s,vector<pair<char,ll>> &p){
  ll x=1;
  if(s.size()==1){
    p.push_back(pair<char,ll>(s[0],1));
  }
  for(ll i=0;i<s.size()-1;i++){
    if(s[i]==s[i+1]){
      x++;
      if(i==s.size()-2){
        p.push_back(pair<char,ll>(s[i],x));
      }
    }else{
      p.push_back(pair<char,ll>(s[i],x));
      x=1;
      if(i==s.size()-2){
        p.push_back(pair<char,ll>(s[s.size()-1],x));
      }
    }
  }
}




ll COM(ll n,ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

const int MAX_N=100010;
vector<bool> sieve_of_eratosthenes(){
  vector<bool> isPrime(MAX_N+1,true);
  for(int i=2;i<=MAX_N;i++){
    if(isPrime[i]){
      for(int j=2*i;j<=MAX_N;j+=i){
        isPrime[j]=false;
      }
    }
  }
  return isPrime;
}

vector<pint> prime_factorize(ll n){
  vector<pint> ans;
  for(ll p=2;p<=sqrt(n);p++){
    if(n%p!=0) continue;
    ll cnt=0;
    while(n%p==0){
      n/=p;
      cnt++;
    }
    ans.push_back(make_pair(p,cnt));
  }
  if(n!=1) ans.push_back(make_pair(n,1));
  return ans;
}

vector<ll> tree[200005];
ll value[200005]={0};
void dfs(ll pre,ll com,ll sum){
  value[com]+=sum;
  for(auto tmp:tree[com]) if(pre!=tmp) dfs(com,tmp,value[com]);
}


/*↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓*/
int main() {
  IOS;
  ll n,q;
  cin>>n>>q;
  rep(i,n-1){
    ll a,b;cin>>a>>b;a--;b--;
    tree[a].push_back(b);
    tree[b].push_back(a);
  }
  rep(i,q){
    ll a,b;cin>>a>>b;a--;
    value[a]+=b;
  }
  dfs(-1,0,0);
  rep(i,n){
    cout<<value[i]<<' ';
  }
  cout<<endl;
  
  
}

Measured memory_bytes: 26240
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <numeric>

using namespace std;
typedef long long ll;

int main(){

  int x, y, z;
  cin >> x >> y >> z;
  if ((x - (y + z) * (x / (y + z))) >= z){
    cout << (x / (y + z)) << endl;
  }
  else {
    cout << (x / (y + z)) - 1 << endl;
  }

  return 0;
}


Measured memory_bytes: 256
f=lambda:[*map(int,input().split())]
n,l,q=f()[0],f(),f()[0]
from collections import *
C=Counter(l)
s=sum(C.elements())
for _ in range(q):
  b,c=f()
  s+=(c-b)*C[b]
  C[c]+=C[b]
  C[b]=0
  print(s)

Measured memory_bytes: 23936
import numpy as np
from heapq import heappush, heappop


x, y, z = map(int, input().split())
n = x + y + z

a = np.zeros((n, ), dtype=np.int64)
b = np.zeros((n, ), dtype=np.int64)
c = np.zeros((n, ), dtype=np.int64)

for i in range(n):
    a[i], b[i], c[i] = map(int, input().split())

sub_ab = b-a

idx_arg = np.argsort(sub_ab)

pq_left = []
pq_right = []

mem = 0

cls = np.zeros((n, ), dtype=np.int64)


for i in range(x):
    mem += a[idx_arg[i]]
    heappush(pq_left, (a[idx_arg[i]]-c[idx_arg[i]], idx_arg[i]))
    cls[idx_arg[i]] = 1

for i in range(x, n):
    mem += c[idx_arg[i]]
    cls[idx_arg[i]] = 3
    heappush(pq_right, (c[idx_arg[i]]-b[idx_arg[i]], idx_arg[i]))
    if(len(pq_right) > z):
        _, idx = heappop(pq_right)
        mem -= c[idx]
        mem += b[idx]
        cls[idx] = 2

ans = mem


for i in range(x, x+z):
    if cls[idx_arg[i]] == 2:
        mem -= b[idx_arg[i]]
        while True:
            _, idx = heappop(pq_right)
            if cls[idx] == 3:
                mem -= c[idx]
                mem += b[idx]
                cls[idx] = 2
                break
    elif cls[idx_arg[i]] == 3:
        mem -= c[idx_arg[i]]
    cls[idx_arg[i]] = 1
    mem += a[idx_arg[i]]
    heappush(pq_left, (a[idx_arg[i]]-c[idx_arg[i]], idx_arg[i]))
    _, idx = heappop(pq_left)
    mem -= a[idx]
    mem += c[idx]
    cls[idx] = 0
    ans = max(ans, mem)

print(ans)


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



int main() {
  int n;
  ll h;
  cin >>n >>h;
  ll count=0;
  ll a[n],b[n];
  ll am=0;//刀を振る時の最大ダメージ
  rep(i,n){
    cin >> a[i] >> b[i];
    am=max(a[i],am);
  }
  sort(b,b+n);

  for(int i=n-1;i>=0;i--){
    if(b[i]<=am)break;
    count++;
    h-=b[i];
    if(h<=0)break;
  }
  if(h>0){count+=(am+h-1)/am;}

  cout << count << endl;

}

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

int n, m, total,cnt = 0;
int a[100];

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

	for (int i = 0; i < n; i++) {
		cin >> a[i];
		total += a[i];
	}
	for (int i = 0; i < n; i++) {
		if (a[i] >= (float)total / (4.0 * (float)m)) {
			cnt++;
		}
	}

	if (cnt >= m) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n=scan.nextInt();
		scan.nextLine();
		String s=scan.nextLine();
		if(n<3200) System.out.println("red");
		else System.out.println(s);

	}

}


Measured memory_bytes: 26972
#include<iostream>
#define MAXN 10
using namespace std;

int N;
int K;
int D[MAXN];
int ans;

bool checkDigit(int n) {
	while (n != 0) {
		for (int i = 0; i < K; i++) {
			if (n % 10 == D[i]) {
				return false;
			}
			//else if (n % 10 > D[i]) {
			//	break;
			//}
		}
		n /= 10;
	}
	return true;
}

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

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

	ans = N;
	while (true) {
		if (checkDigit(ans)) {
			cout << ans << endl;
			return 0;
		}
		ans++;
	}

}

Measured memory_bytes: 256
using System;

namespace abc124B
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int[] H = new int[N];
            string[] str = Console.ReadLine().Split();
            for (int i = 0; i < N; i++)
            {
                H[i] = int.Parse(str[i]);
            }
            int A = 1;
            int B = H[0];
            for(int i = 1; i < N; i++)
            {
                if (H[i - 1] > H[i])
                {
                    H[i] = H[i - 1];
                }
                else
                    A = A + 1;
            }
            Console.WriteLine(A);
        }
    }
}


Measured memory_bytes: 11220
import java.util.Scanner;

public class Main{
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        while(true){
            int x = sc.nextInt();
            int y = sc.nextInt();
            if(x == 0 && y == 0)
                break;
            int n = 0;
            if(x>y){
                n = x;
                x = y;
                y = n;
            }
            System.out.println(x + " " + y);
        }
    }
}
                


Measured memory_bytes: 36104
x,y,z = map(int,input().split())
y %= 4
if y == 0:
    if z % 4 ==0:
        print("YES")
        exit()
if y == 1:
    if z % 4 == 2:
        print("YES")
        exit()
if y == 2:
    if z % 4 == 0:
        print("YES")
        exit()
if y == 3:
    if z % 4 == 2:
        print("YES")
        exit()
print("NO")

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

int main(){
  string c = "Yes";
  int n,cnt=0;
  cin >> n;
  int a[n];
  for(int i=0;i<n;i++)
    cin >> a[i];
  for(int i=n-1;0<i;i--){
    if(a[i]-a[i-1]<-1) {c = "No"; break;}
    else if(a[i]-a[i-1]>-1) continue; 
    else if(a[i]-a[i-1]==-1) a[i-1]--;
  }
  cout << c << endl;
}

Measured memory_bytes: 640
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())




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

	int n;
	cin>>n;
	int ans=0,len=0;
	int p;
	rep(i,n){
		cin>>p;
		if (p==i+1){
			len++;
		}
		else{
			ans += (len+1)/2;
			len=0;
		}
	}

	ans += (len + 1) / 2;
	len = 0;
	
	cout<<ans<<endl;

	return 0;
}

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

int main(){
    int N;
    cin >> N;
    ll A[100000], B[100000];
    for(int i=0;i<N;i++)
        cin >> A[i] >> B[i];
    
    ll ans = 0;
    for(int i=N-1;i>=0;i--){
        A[i] += ans;
        ans += (B[i] - A[i] % B[i]) % B[i];
    }

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

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

int putere(int n)
{
    long long ans = 1;
    for (int i = 1; i <= n; i++)
    {
        ans *= 10;
    }
    return ans;
}

int nrcif(int n)
{
    int cntr = 0;
    while (n)
    {
        cntr++;
        n /= 10;
    }
    return cntr;
}

bool pp(int n)
{
    if (sqrt(n) == int (sqrt(n)))
    {
        return 1;
    }
    else
    {
        return 0;
    }
}


int main()
{
    int a, b;
    long long nr = 0;
    cin >> a >> b;
    nr = a * putere(nrcif(b)) + b;
    if (pp(nr) == 1)
        cout << "Yes";
    else
        cout << "No";
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
#include <tuple>

#define DEBUG(x) cout<<#x<<": "<<x<<endl

using namespace std;

int main(){

	int a[5];
	long sum = 0;

	for(int i = 0; i<5; i++)
		cin >> a[i];

	for(int i = 0; i<5; i++){
		sum += a[i]/10;
		a[i] %= 10;
	}
	sum*= 10;

	sort(a, a+5);

	bool flag = true;
	for(int i = 0; i<5; i++){
		if(a[i] == 0){
		} else if(flag == true){
			sum += a[i];
			flag = false;
		} else {
			sum += 10;
		}
	}

	cout << sum << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <cmath>
#include <numeric>
#include <iomanip>
#include <deque>
#include <tuple>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <sstream>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define pb push_back
#define pf push_front

namespace mp = boost::multiprecision;
using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;

ll M = 1000000007;
template <class T>
void print(const T &value)
{
	std::cout << value << std::endl;
}
int GCD(int x, int y)
{
	return x ? GCD(y % x, x) : y;
}

int main()
{
	int n,cnt=0;
	cin>>n;
	map<int,int>al;
	rep(i,n){
		int u;
		cin>>u;
		if(al[u]==0){
			al[u]++;
		}else{
			cnt++;
		}
	}
	if(cnt%2==1){
		cnt++;
	}
	cout<<n-cnt<<endl;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int maxN = 1e5+7;
const int maxM = 1e5+7;
const int maxV = 90010;
//const int INF = 1e9+9;
const ll INF = (1ll)<<60;
//const int INF = 2e9+9;
const int MOD = 1e9+7;

int n,x,y; 
int a[maxN];

int main()
{
    scanf("%d%d%d",&n,&x,&y);
 	int ans = 0;
 	if(n*x > y)
 		ans = y;
 	else
 		ans = n*x;
 	cout<<ans<<endl; 
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
#include <vector>

using boost::multiprecision::cpp_int;
using namespace std;

#if __has_include("print.hpp")
  #include "print.hpp"
#endif

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MOD 1000000007

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

typedef long long ll;
typedef pair<ll, ll> p;


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n;
  cin >> n;
  vector<ll> v(n);
  map<ll, ll> mp;
  ll sum = 0;
  rep(i, n) {
    cin >> v[i];
    mp[v[i]]++;
  }
  for(auto a : mp){
    sum += ((a.second - 1)*a.second) / 2;
  }

  rep(i, n){
    ll k = v[i];
    sum -= ((mp[k]-1)*mp[k]) / 2;
    sum += ((mp[k]-1)*(mp[k]-2)) / 2;
    cout << sum << endl;
    sum -= ((mp[k]-1)*(mp[k]-2)) / 2;
    sum += ((mp[k]-1)*mp[k]) / 2;
  }
}


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

constexpr int LEN = 105;
int a[LEN][LEN];

int dikstra(int g, const int n){
	int d[n];
	bool check[n] = {0};
	memset(d, 1, sizeof(d));
	d[0] = 0;

	while(true){
		int u;
		int min_cost = INT_MAX;
		rep(i, n){
			if(!check[i] && (d[i] < min_cost)) {
				min_cost = d[i];
				u = i;
			}
		}

		if(min_cost == INT_MAX) break;
		check[u] = true;

		rep(v, n){
			if(!check[v] && (a[u][v] > -1)){
				if((d[u] + a[u][v]) < d[v]){
					d[v] = d[u] + a[u][v];
				}
			}
		}
	}

	return d[g];
}

int main(){
	memset(a, -1, sizeof(a));
	int n; cin >> n;
	rep(i, n){
		int u, k; cin >> u >> k;
		rep(j, k){
			int v, c; cin >> v >> c;
			a[u][v] = c;
		}
	}

	rep(i, n) cout << i << ' ' << dikstra(i, n) << endl;

	return 0;
}



Measured memory_bytes: 3144
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
#define ll long long
ll dp[2010];

int main()
{
    int n;
    cin >> n;
    
    dp[0]=dp[1]=dp[2]=0;
    dp[3]=dp[4]=dp[5]=1;
    
    for(int i=6;i<=n;++i)
    {
        ll sum=0;
        for(int j=1;j<=i-3;++j)
        {
            sum+=dp[j]%mod;
        }
        (dp[i]+=sum+1)%=mod;
    }
    cout << dp[n] << "\n";
    
    return 0;
}


Measured memory_bytes: 3644
open System

let n = Console.ReadLine() |> int

let testimonies: (int * int) list list =
    [ for i in 1 .. n do
        let a = Console.ReadLine() |> int
        yield [ for j in 1 .. a do
                    let xy = Console.ReadLine().Split(' ') |> Array.map int
                    yield xy.[0] - 1, xy.[1] ] ]

let ans =
    let rec dfs is rest =
        match rest with
        | [] ->
            let set = Set is

            let ok =
                is
                |> List.map (fun i ->
                    testimonies.[i]
                    |> List.forall (fun testimony ->
                        let x, y = testimony
                        (y = 0 && not (set.Contains x)) || (y = 1 && set.Contains x)))
                |> List.forall (fun b -> b)

            if ok then List.length is else 0
        | i :: rest ->
            max (dfs is rest) (dfs (i :: is) rest)

    dfs [] [ 0 .. n - 1 ]

ans |> Console.WriteLine


Measured memory_bytes: 20572
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int tarou = 0;  //太郎の得点
		int hanako = 0;  //花子の得点
		int n = sc.nextInt();

		for(int i = 0; i < n; i++) {
			String taro = sc.next();
			String hana = sc.next();

			if(taro.equals(hana)) {  //同じ単語の場合
				tarou++;
				hanako++;
			}
			else {  //別な単語の場合、配列に変換し先頭から1文字ずつ比較
				char ta[] = taro.toCharArray();
				char ha[] = hana.toCharArray();
				boolean frag = false;  //for文をbreakで出たのかどうか判定
				for(int j = 0; j < Math.min(taro.length(), hana.length()); j++) {
					if(ta[j] > ha[j]) {
						tarou += 3;
						frag = true;
						break;
					}
					else if(ta[j] < ha[j]) {
						hanako += 3;
						frag = true;
						break;
					}
				}
				if(frag == false) {  //breakで出ていない場合
					if(taro.length() > hana.length()) tarou += 3;  //長さ比較で長いほうが+3
					else hanako += 3;
				}
			}
		}

		System.out.println(tarou + " " + hanako);
	}

}



Measured memory_bytes: 29692
#include <unordered_map>
#include <chrono>
#include <random>
#include <algorithm>
#include <cstdint>
#include <cstring>
#include <cstdio>
using namespace std;

static const int Maxn = 155;

struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};

int n, k, mod;
inline int add(int x, int y) { return (x += y) >= mod ? x - mod : x; }
inline void inc(int &x, int y) { (x += y) >= mod && (x -= mod); }
inline int mul(int x, int y) { return 1LL * x * y - 1LL * x * y / mod * mod; }

namespace solve1 {
/* N个数中选一些数使得连续段的长度不超过K */
  int dp[Maxn][Maxn];
  int solve(int n, int k) {
  memset(dp, 0, sizeof(dp));
  dp[0][0] = 1;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= k; ++j) {
      inc(dp[i + 1][0], dp[i][j]);
    }
    for (int j = 0; j < k; ++j) {
      inc(dp[i + 1][j + 1], dp[i][j]);
    }
  }
  int res = 0;
  for (int j = 0; j <= k; ++j) {
    inc(res, dp[n][j]);
  }
  return res;
  }
}

namespace solve2 {
  int n, k;
  unordered_map<long long, int, custom_hash> dp[Maxn];
  inline long long encode(int p, int q, int mxp, int mxq) {
    return (p * 1LL << 40) | (q * 1LL << 30) | (mxp * 1LL << 20) | (mxq * 1LL << 10);
  }
  int dfs(int pos, int p, int q, int mxp, int mxq) {
    if (mxp < pos || mxq < pos) return 0;
    if (pos == n) return 1;
    p = min(p, k / 2 + 1);
    q = min(q, k / 2 + 1);
    long long enc = encode(p, q, mxp, mxq);
    if (dp[pos].find(enc) != dp[pos].end()) return dp[pos][enc];
    int &ans = dp[pos][enc]; ans = 0;
    int res1, res2;

// 填入数pos
    int newmxp = n, newmxq = n;
    if (pos % 2 == 0 && 2 * q - 1 >= k) newmxq = pos + k - 2 * min(k / 2, p);
    if (pos % 2 == 1 && 2 * p - 1 >= k) newmxp = pos + k - 2 * min(k / 2, q);
    int newp = p + (pos % 2 == 0), newq = q + (pos % 2 == 1);
    res1 = dfs(pos + 1, newp, newq, min(mxp, newmxp), min(mxq, newmxq));

// 不填数pos
    if (pos % 2 == 0) res2 = dfs(pos + 1, 0, q, n, mxq);
    else res2 = dfs(pos + 1, p, 0, mxp, n);

    return ans = add(res1, res2);
  }
  int solve(int n, int k) {
    solve2::n = n, solve2::k = k;
    for (int i = 0; i <= n; ++i) {
      unordered_map<long long, int, custom_hash> empty_tmp;
      dp[i].swap(empty_tmp);
    }
    return dfs(0, 0, 0, n, n);
  }
}

int main() {
  scanf("%d%d%d", &n, &k, &mod);
  if (k == 1) {
    printf("%d\n", solve1::solve(n, 2));
    return 0;
  }
  if (k % 2 == 0) {
    int odd = solve1::solve(n + 1 >> 1, k >> 1);
    int even = solve1::solve(n >> 1, k >> 1);
    printf("%d\n", mul(odd, even));
    return 0;
  }
  printf("%d\n", solve2::solve(n, k));
  return 0;
}


Measured memory_bytes: 17280
n,k = gets.chomp.split().map(&:to_i)

if k == 0
  puts n*n
  exit
end

ans = 0
(k+1).upto(n).each do |b|
  tani = b - k
  katamari = (n+1) / b
  nokori = [(n+1) % b - k, 0].max

  # tani * katamari

  ans += tani * katamari + nokori
end

puts ans

Measured memory_bytes: 1916
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x)          (x).begin(), (x).end()
#define rep(i, n)       for (i64 i = 0, i##_limit = (n); i < i##_limit; ++i)
#define reps(i, s, t)   for (i64 i = (s), i##_limit = (t); i <= i##_limit; ++i)
#define repr(i, s, t)   for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#ifndef DBG
#define trace(...)
#endif
using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T, class U> inline bool chmax(T &a, const U &b) { return b > a && (a = b, true); }
template <class T, class U> inline bool chmin(T &a, const U &b) { return b < a && (a = b, true); }
constexpr int INF  = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

template <class T>
inline vector<T> make_v(const T &initValue, size_t sz) {
    return vector<T>(sz, initValue);
}

template <class T, class... Args>
inline auto make_v(const T &initValue, size_t sz, Args... args) {
    return vector<decltype(make_v<T>(initValue, args...))>(sz, make_v<T>(initValue, args...));
}

template <class T>
inline istream& operator>> (istream &in, vector<T> &vec) {
    for (auto &e : vec) in >> e;
    return in;
}

inline void read() {}

template <class Head, class... Tail>
inline void read(Head &head, Tail&... tail) { cin >> head; read(tail...); }

inline void print() { cout << "\n"; }

template <class Head, class... Tail>
inline void print(Head &&head, Tail&&... tail) {
    cout << head;
    if (sizeof...(tail)) cout << ' ';
    print(forward<Tail>(tail)...);
}

template <class T>
inline ostream& operator<< (ostream &out, const vector<T> &vec) {
    static constexpr const char *delim[] = { " ", "" };
    for (const auto &e : vec) out << e << delim[&e == &vec.back()];
    return out;
}
// }}} End Header

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    string s;
    read(s);
    const int N = s.length();

    stack<char> st;
    rep(i, N) {
        if (!st.empty() && st.top() == 'S' && s[i] == 'T') {
            st.pop();
        } else {
            st.push(s[i]);
        }
    }

    print(st.size());

    return 0;
}


Measured memory_bytes: 720
#include<cstdio>
#include<algorithm>
#define LL long long 
int lena,lenb,a[100],b[100],n;
char s[50];
LL ans,f[50][50];
using namespace std;
void pan()
{
	f[n][1]=(s[b[lenb]]==s[n]);
	f[n][0]=(s[a[lena]]==s[n]);
	for (int i=n+1;i<n*2;i++)
	  for (int j=0;j<=min(i-n+1,lenb);j++)
	  {
	  	f[i][j]=0;
	  	if (lena>0)
	  	if (j<i-n+1)
	  	if (s[a[lena-i+n+j]]==s[i]) f[i][j]+=f[i-1][j];
	  	if (j>=1)
	  	if (lenb>0)
	  	if (s[i]==s[b[lenb-j+1]]) f[i][j]+=f[i-1][j-1];
	  }
	ans+=f[n*2-1][lenb]; 
}
void dfs(int x)
{
	if (x>=n)
	{
		pan(); 
	}
	else
	{
		lena++; a[lena]=x; dfs(x+1); lena--;
		lenb++; b[lenb]=x; dfs(x+1); lenb--; 
	}
}
int main()
{
	scanf("%d",&n);
	scanf("%s",s);
    dfs(0);
    printf("%lld",ans);
}

Measured memory_bytes: 128