akhauriyash/Code-Regression huggingface dataset:
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue
# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, k = ns()
    a = na()

    for _ in range(k):
        imos = [0 for _ in range(n)]

        for i, ai in enumerate(a):
            imos[max(0, i - ai)] += 1
            if i + ai + 1 < n:
                imos[i + ai + 1] -= 1

        val = 0
        for i, im in enumerate(imos):
            val += im
            a[i] = min(val, n)

        if min(a) == n:
            break

    print(*a, sep=" ")


if __name__ == '__main__':
    main()


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

int main() {
  int n;
  cin>>n;
  int a[n];
  rep(i,n) cin>>a[i];
  int b=0,c=0,d=0;
  ll ans=1;
  rep(i,n){
    int cnt=0;
    if(b==a[i]) cnt++;
    if(c==a[i]) cnt++;
    if(d==a[i]) cnt++;
    ans*=cnt;
    ans%=mod;
    if(b==a[i]) b++;
    else if(c==a[i]) c++;
    else d++;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

const int LIM = 105;
int n, w;
int q[LIM];
long long ans = 0, sum[100005], v[LIM];


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

    for(int i = 1; i <= n; ++i) 
        cin >> q[i] >> v[i];
    

    vector <int> s;

    for (int j = 1; j <= n; ++j) {
        vector<pair<int,long long>> modificari;
        ans = max(ans, v[j]);

        int lg = s.size();

        if (sum[q[j]] == 0)  //daca nu exista o multime cu a j greutate, o punem in sirul de multimi
            s.push_back(q[j]);

        for (int k = 0; k < lg; ++k) {

            if (s[k] + q[j] <= w){ //daca greutatea se incadreaza in W

                if (sum[s[k] + q[j]] == 0) // daca nu am greutatea multime + element nou in sir
                    s.push_back(s[k] + q[j]);

                modificari.push_back(make_pair(s[k] + q[j], sum[s[k]] + v[j]));

                ans = max(ans, sum[s[k]] + v[j]);
            }
        }
        sum[q[j]] = max(sum[q[j]], v[j]);

        for (size_t i = 0; i < modificari.size(); ++i) 
            sum[modificari[i].first] = max(sum[modificari[i].first], modificari[i].second);
    }


    cout << ans;
    return 0;
}


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

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

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

	int h,w;
	cin >> h >> w;

	int n;
	cin >> n;

	int a[n];
	rep(i,n) cin >> a[i];

	int grid[h][w];

	int x = 0;
	int y = a[0];

	rep(i,h*w){
		if(x < n-1 && i+1 > y){
			x++;
			y += a[x];
		}

		int s = i / w;
		int t = (s % 2 == 0 ? i % w : w - i % w - 1);
		grid[s][t] = x+1;
	}
	
	rep(i,h){
		cout << grid[i][0];
		rep(j,w-1){
			cout << " " << grid[i][j+1];
		}
		cout << endl;
	}
}

Measured memory_bytes: 384
import std.algorithm;
import std.array;
import std.conv;
import std.stdio;
import std.string;

immutable int NA = -1;

int [] solve (int [] x)
{
	int n = cast (int) (x.length);
	auto a = new int [n * n];
	a[] = NA;
	int [2] [] v;
	foreach (int i, c; x)
	{
		v ~= [c, i];
	}
	sort (v);
	int [] pos;
	int [] lo;
	int [] hi;
	foreach (int i, c; x)
	{
		a[c] = i;
		pos ~= c;
		lo ~= i;
		hi ~= n - i - 1;
	}

main_loop:
	foreach (i; 0..n * n)
	{
		if (a[i] != NA)
		{
			if (lo[a[i]] != 0)
			{
				return [];
			}
			continue;
		}

		foreach (j; 0..n)
		{
			int cur = v[j][1];
			if (pos[cur] < i)
			{
				continue;
			}
			if (lo[cur] == 0)
			{
				continue;
			}
			a[i] = cur;
			lo[cur] -= 1;
			continue main_loop;
		}

		foreach_reverse (j; 0..n)
		{
			int cur = v[j][1];
			if (pos[cur] > i)
			{
				continue;
			}
			if (hi[cur] == 0)
			{
				continue;
			}
			a[i] = cur;
			hi[cur] -= 1;
			continue main_loop;
		}

		return [];
	}

	return a;
}

void main ()
{
	int n;
	while (readf (" %s", &n) > 0)
	{
		readln;
		auto x = readln.split.map !(to !(int)).array;
		x[] -= 1;
		auto a = solve (x);
		if (a.empty)
		{
			writeln ("No");
		}
		else
		{
			writeln ("Yes");
			a[] += 1;
			writefln ("%(%s %)", a);
		}
	}
}


Measured memory_bytes: 2172
n, k = map(int, input().split())
hs = []
diff = []

for i in range(n):
    h = int(input())
    hs.append(h)

hs.sort()

for i in range(n - k + 1):
    diff.append(hs[i + k - 1] - hs[i])
    
print(min(diff))

Measured memory_bytes: 11288
#include <bits/stdc++.h>
using namespace std;
 
int main () {
  int N, M;
  cin >> N >> M;  
  int list[N];
  for(int i = 0; i<N; i++) cin >> list[i];
  int cnt = 0;
  for(int i = 0; i<N; i++) cnt += list[i];
  sort(list , list + N, greater<int>());
 
  int res = 0;
  for(int i = 0; i<N; i++) {
    if(list[i] * (4*M) >= cnt) res++;
  }
 
  if(res >= M) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

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


int main() {
	int k, s, c=0;
	cin>>k>>s;
	for(int i=0; i<=k; i++){
		for(int j=0; s-i-j>=0 && j<=k; j++){
			if(s-i-j<=k ) c++;
		}
	}
	cout<<c;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//#include <atcoder/all>
#define ll long long int
#define MOD 1000000007
#define P pair<ll,ll>
#define INF 1000000000000000000

//using namespace atcoder;
using namespace std;

string transform(string t, ll x, ll y){
  for (ll i = 0; i < t.size(); i++){
    if (t[i] == 'R' && x < 0){
      t[i] = 'L'; 
    }
    else if (t[i] == 'L' && x < 0){
      t[i] = 'R'; 
    }
    else if (t[i] == 'U' && y < 0){
      t[i] = 'D'; 
    }
    else if (t[i] == 'D' && y < 0){
      t[i] = 'U'; 
    }
  }
  return t;
}

int main(void){
  ll sx, sy, tx, ty;
  cin >> sx >> sy >> tx >> ty;
  
  tx -= sx;
  ty -= sy;

  sx = tx;
  sy = ty;

  tx = abs(tx);
  ty = abs(ty);

  string t = "";
  // 1周目
  for (ll i = 0; i < ty; i++){
    t += "U";
  }
  for (ll i = 0; i < tx; i++){
    t += "R";
  }
  for (ll i = 0; i < ty; i++){
    t += "D";
  }
  for (ll i = 0; i < tx; i++){
    t += "L";
  }

  // 1周目
  t += "L";
  for (ll i = 0; i < ty + 1; i++){
    t += "U";
  }
  for (ll i = 0; i < tx + 1; i++){
    t += "R";
  }
  t += "D";
  t += "R";
  for (ll i = 0; i < ty + 1; i++){
    t += "D";
  }
  for (ll i = 0; i < tx + 1; i++){
    t += "L";
  }
  t += "U";

  cout << transform(t, sx, sy) << endl;
  for (ll i = 0; i < ty; i++){
    t += "D";
  }
  for (ll i = 0; i < tx; i++){
    t += "L";
  }



  return 0;
}


Measured memory_bytes: 3656
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<queue>
#include<stack>
#include<complex>
#include<utility>
#include<cmath>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define pi acos(-1)
#define all(v) v.begin(),v.end()
using namespace std;

const double eps = 1e-8;
const double INF = 1e12;

typedef pair<int,int> P;
typedef double Real;
typedef complex<Real> Point;
typedef vector<Point> G;

double cross(const Point& a,const Point& b){//calculate ad-bc(vector product)
	return imag(conj(a)*b);
}

struct L:public vector<Point>{//line data
	L(const Point &a,const Point &b){
		push_back(a);
		push_back(b);
	}
};

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

int main(){
	string s[12];
	int dt[12][12];
	while(cin>>s[0]){
		loop(i,1,12)cin>>s[i];
		rep(i,12){
			rep(j,12){
				dt[i][j]=(int)(s[i][j]-'0');
			}
		}
		int ans=0;
		rep(i,12){
			rep(j,12){
				if(dt[i][j]){
					ans++;
					queue<P> que;
					P now(j,i);
					que.push(now);
					while(!que.empty()){
						now=que.front();
						que.pop();
						if(now.second>=12 ||now.first<0 || now.second<0 || now.first>=12)continue;
						if(dt[now.second][now.first]==0)continue;
						dt[now.second][now.first]=0;
						rep(k,4){
							now.first+=dx[k];
							now.second+=dy[k];
							que.push(now);
							now.first-=dx[k];
							now.second-=dy[k];
						}
					}
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 1208
import java.util.*;


public class Main {
  static final long MOD = 1000000007;
  static int H, W, A, B;
  static long[] fact, ifact;

  public static long modInv(long n) {
    return (euqlidNormal(MOD, n)[1] + MOD) % MOD;
  }

  public static long[] euqlidNormal(long a, long b) {
    long ret[] = new long[2];
    long q = a / b;
    long r = a % b;
    if(r == 1) {
      ret[0] = 1;
      ret[1] = -q;
    } else {
      long[] rec = euqlidNormal(b, r);
      ret[0] = rec[1];
      ret[1] = rec[0] - q * rec[1];
    }
    return ret;
  }

  public static long path(int h, int w) {
    long l = fact[h + w - 2];
    l = (l * ifact[h - 1]) % MOD;
    l = (l * ifact[w - 1]) % MOD;
    return l;
  }

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

    H = sc.nextInt();
    W = sc.nextInt();
    A = sc.nextInt();
    B = sc.nextInt();

    fact = new long[H + W + 1];
    ifact = new long[H + W + 1];
    fact[0] = 1;
    fact[1] = 1;
    ifact[0] = 1;
    ifact[1] = 1;
    for(int i = 2; i <= H + W; i++) {
      fact[i] = i * fact[i - 1] % MOD;
      ifact[i] = modInv(fact[i]);
    }

    long n = 0;
    for(int i = 1; i <= H - A; i++) {
      n += (path(i, B) * path(H - i + 1, W - B)) % MOD;
      n %= MOD;
    }

    System.out.println(n);
  }
}


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

int main() {
  string s;
  cin >> s;
  int n=s.size();
  
  bool judge=true;
  for(int i=0; i<(n-1)/2; i++){
    if(s.at(i)!=s.at(n-1-i)){
      judge=false;
      break;
    }
  }
  
  if(judge){
    for(int i=0; i<n/2; i++){
      if(s.at(i)!=s.at((n-1)/2-1-i)){
        judge=false;
        break;
      }
    }
  }
  
  if(judge){
    int j=0;
    for(int i=(n+3)/2-1; i<n; i++){
      if(s.at(i)!=s.at(n-1-j)){
        judge=false;
        break;
      }
      j++;
    }
  }
  if(judge){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <iomanip>
#include <stack>
#include <vector>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <queue>
#include <set>
#include <limits>
#include <numeric>
#include <array>
using namespace std;
struct Node
{
	vector<int> connectedVertices;
	int maxLength;
};

int main()
{
	int vertices, edges;
	cin >> vertices;
	cin >> edges;
	vector<int> indegrees(vertices);
	unordered_map<int, Node> graph;
	for (int i = 0; i < vertices; ++i)
	{
		graph[i];
	}

	for (int i = 0; i < edges; ++i)
	{
		int parent, child;
		cin >> parent;
		cin >> child;
		--child;
		--parent;
		++indegrees[child];
		graph[parent].connectedVertices.push_back(child);
	}

	queue<int> q;
	for (const auto& node : graph)
	{
		if (indegrees[node.first] == 0)
		{
			q.push(node.first);
		}
	}

	while (!q.empty())
	{
		int size = q.size();
		for (int i = 0; i < size; ++i)
        {
		    auto parent = q.front();
		    q.pop();
			for (auto child : graph[parent].connectedVertices)
			{
				graph[child].maxLength = max(graph[child].maxLength, graph[parent].maxLength + 1);
				--indegrees[child];
				if(indegrees[child] == 0) q.push(child);
			}
	    }
	}

	cout << max_element(graph.begin(), graph.end(), 
		[](const auto& item1, const auto& item2) 
	{
		return item1.second.maxLength < item2.second.maxLength; 
	})->second.maxLength;
	return 0;
}

Measured memory_bytes: 11044
N = gets.to_i
S = gets.chomp.chars
w_count = 0
e_count = 0
S.each do |ch|
  if ch == 'W'
    w_count += 1
  else
    e_count += 1
  end
end
counts = Array.new(N)
S.each.with_index do |ch, i|
  wc = ch == 'W' ? 1 : 0
  ec = ch == 'E' ? 1 : 0
  if i == 0
    counts[i] = [wc, ec]
  else
    pwc, pec = counts[i - 1]
    counts[i] = [pwc + wc, pec + ec]
  end
end

ans = 1 << 60
N.times do |i|
  lwc, lec = counts[i]
  rwc = w_count - lwc
  rec = e_count - lec
  count = if S[i] == 'W'
    lwc - 1 + rec
  else
    lwc + rec
  end
  ans = count if count < ans
end
puts ans


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

int main(){
    int N;
	cin >> N;
    vector<string> S(N);
    for(int i=0; i<N; i++){
        cin >> S.at(i);
    }

    int ac=0;
    int wa=0;
    int tle=0;
    int re=0;
    for(int i=0; i<N; i++){
        if( S.at(i) == "AC" ){
             ac++;
        }
        else if( S.at(i) == "WA" ){
             wa++;
        }
        else if( S.at(i) == "TLE" ){
             tle++;
        }
        else if( S.at(i) == "RE" ){
            re++;
        }
    }

	cout << "AC x " << ac << endl;
	cout << "WA x " << wa << endl;
	cout << "TLE x " << tle << endl;
	cout << "RE x " << re << endl;

}


Measured memory_bytes: 6424
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
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; }
typedef long long ll;
typedef pair<int,int> P;

int main(){
    int n;
    cin >> n;
    vector<string> v[20];
    for(int i=1;i<10;i++)v[1].push_back(to_string(i));
    // if(n<10){
    //     cout << n << endl;
    //     return 0;
    // }
    for(int i=2;i<13;i++){
        for(auto s:v[i-1]){
            if(s[i-2]!='0')v[i].push_back(s+to_string(s[i-2]-'0'-1));
            v[i].push_back(s+to_string(s[i-2]-'0'));
            if(s[i-2]!='9')v[i].push_back(s+to_string(s[i-2]-'0'+1));
        }
    }
    int id = n;
    for(int i=1;i<13;i++){
        if(id<v[i].size()){
            cout << v[i][id-1] << endl;
            return 0;
        }
        else {
            id -= v[i].size();
        }
    }
}

Measured memory_bytes: 100712
#include <iostream>
#include <vector>
using namespace std;
int main(){
    int h,w;
    cin>>h>>w;
    
    vector<string> s(h);
    for(int i=0;i<h;i++){
        cin>>s[i];
    }
    vector<vector<char>> sv(h+2,vector<char>(w+2,'0'));
    
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(s[i][j]=='#'){
                sv[i+1][j+1]='#';
                
                if(sv[i][j]!='#') sv[i][j]+=1;
                if(sv[i][j+1]!='#') sv[i][j+1]+=1;
                if(sv[i][j+2]!='#') sv[i][j+2]+=1;
                if(sv[i+1][j]!='#') sv[i+1][j]+=1;
                if(sv[i+1][j+2]!='#') sv[i+1][j+2]+=1;
                if(sv[i+2][j]!='#') sv[i+2][j]+=1;
                if(sv[i+2][j+1]!='#') sv[i+2][j+1]+=1;
                if(sv[i+2][j+2]!='#') sv[i+2][j+2]+=1;
            }
        }
    }
    
    for(int i=1;i<h+1;i++){
        for(int j=1;j<w+1;j++){
            cout<<sv[i][j];
        }
        cout<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
const int inf = 1e9 + 7;
const ll INF = 1e18;
const int mod = 1000000007;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
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); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<typename T> T pow(T a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
ll modpow(ll a, ll b, ll _mod) { return b ? modpow(a * a % _mod, b / 2, _mod) * (b % 2 ? a : 1) % _mod : 1; }
template<class T> ostream& operator << (ostream& os, const vector<T>& vec) { for (auto &vi: vec) os << vi << " "; return os; }
template<class T, class U> ostream& operator << (ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
template<typename T >inline istream& operator >> (istream& is, vector<T>& v) { rep(j, sz(v)) is >> v[j]; return is; }
template<class T> inline void add(T &a, int b) { a += b; if (a >= mod) a -= mod; }


void solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(10);

    int T;
    // cin >> T;
    T = 1;

    while (T--) {
        solve();
    }
}


void solve() {
  // ある数が何回 2 番目になるか
  int n;
  cin >> n;
  vector<pii> a(n);
  rep(i, n) { cin >> a[i].F; a[i].S = i; }
  // すべての値が distinct
  sort(all(a), greater<pii>());

  ll ans = 0;

  // 下のコメントアウトとどっちでもいい
  // ll, rr はみ出したときの値使わない
  set<int> s;
  s.insert(-1);
  s.insert(n);
  s.insert(-2);
  s.insert(n + 1);
  /*
  multiset<int> s;
  s.insert(-1);
  s.insert(n);
  s.insert(-1);
  s.insert(n);
  */
  rep(i, n) {
    int j = a[i].S;
    auto rl = s.upper_bound(j);
    // auto rr = --rl; error
    auto rr = rl;
    rr++;

    auto lr = rl;
    lr--;
    auto ll = lr;
    ll--;

    long long tmp = 0; // ll が衝突
    // 左側で i より大きいのとる
    // 右側は i を含んでいい
    if (*lr != -1) tmp = 1LL * (*rl - j) * (*lr - *ll);
    // 右側で
    if (*rl != n) tmp += 1LL * (*rr - *rl) * (j - *lr);
    tmp *= 1LL * a[i].F;
    ans += tmp;
    s.insert(a[i].S);
  }
  cout << ans << endl;
}


Measured memory_bytes: 5760
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001ll
#define fcout cout << fixed << setprecision(10)

using namespace std;

int dp[5005][5005][2];
int sdp[5005][2];
vector<int> G[5005];
int A[5005];
int num[5005];

void dfs(int x, int par) {
    REP(j, G[x].size()) {
        int c = G[x][j];
        if (c == par) continue;
        dfs(c, x);
    }

    REP(i, 5005) sdp[i][0] = sdp[i][1] = INF;

    dp[x][0][A[x] < 0] = A[x];

    int sum = 1;
    REP(j, G[x].size()) {
        int c = G[x][j];
        if (c == par) continue;
        REP(s1, sum) {
            REP(s2, num[c]) {
                REP(k1, 2) {
                    REP(k2, 2) {
                        // つなぐ
                        if (dp[c][s2][k2] < INF) {
                            sdp[s1 + s2][k1 | k2] = min(sdp[s1 + s2][k1 | k2], dp[x][s1][k1] + dp[c][s2][k2]);
                        }

                        // 切る
                        if (dp[c][s2][k2] < 0 || (k2 == 0 && dp[c][s2][k2] < INF)) {
                            sdp[s1 + s2 + 1][k1] = min(sdp[s1 + s2 + 1][k1], dp[x][s1][k1]);
                        }
                    }
                }
            }
        }
        sum += num[c];
        REP(nj, sum) {
            REP(k, 2) {
                dp[x][nj][k] = sdp[nj][k];
                sdp[nj][k] = INF;
            }
        }

    }

    num[x] = sum;
}

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

    int N;
    cin >> N;
    REP(i, N) cin >> A[i];
    REP(i, N - 1) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    REP(i, N) REP(j, N - 1) REP(k, 2) dp[i][j][k] = INF;

    dfs(0, -1);

    int res = INF;
    REP(j, N) {
        if (dp[0][j][0] < INF) res = min(res, j);
        if (dp[0][j][1] < 0) res = min(res, j);
    }
    cout << res << endl;

    return 0;
}


Measured memory_bytes: 392448
#include<bits/stdc++.h>
#include<cctype>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);i++)
#define reps(i,n) for (int i=1;i<=(n);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rreps(i,n) for (int i=(n);i>0;i--)
#define all(v) (v).begin(),(v).end()
#define pi 3.1415926535897932384
#define E9 1000000000
#define eps 1e-4
#define pii pair<int,int>
template<class T> inline bool chmin(T &a, T b) {if (a>b) {a = b; return 1;} return 0;};
template<class T> inline bool chmax(T &a, T b) {if (a<b) {a = b; return 1;} return 0;};
typedef long long int ll;
const long long INF = 1LL << 60;

int main(){
  int N; cin >> N;
  vector<ll> dp(1001000, INF);
  dp[0] = 0;
  rep(i,N){
    chmin(dp[i+1], dp[i]+1);
    for (ll powsix=6;powsix<=N;powsix*=6) chmin(dp[i+powsix], dp[i]+1);
    for (ll pownine=9;pownine<=N;pownine*=9) chmin(dp[i+pownine], dp[i]+1);
  }
  cout << dp[N] << endl;

 

  // cout << fixed << setprecision(10);
  
  return 0;
}


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

int main(){
  string a;
  cin >> a;
  int b = a.size();
    
  for(int i=0;i<b;i++){
    char c = a[i];
    if(i%2 == 0 && c == 'L'){
      cout << "No" << endl;
      return 0;
    }
    if(i%2 == 1 && c == 'R'){
    cout << "No" << endl;
      return 0;
    }
    
  }
  cout << " Yes" << endl;
}

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

int main(){
    int a, b, c, d, e, f;
    cin >> a >> b >> c >> d >> e >> f;
    a = a * 100;
    b = b * 100;

    set<int> water;
    for(int i = 0; i <= 30; i++){
        for(int j = 0; j <= 30; j++){
            if(i != 0 || j != 0){
                if(a * i + b * j <= f){
                    water.insert(a * i + b * j);
                }
            }
        }
    }

    set<int> suger;
    for(int i = 0; i <= 3000; i++){
        for(int j = 0; j <= 3000; j++){
            if(c * i + d * j <= f){
                suger.insert(c * i + d * j);
            }
        }
    }

    vector<pair<int, int>> ans;
    for(auto itr = water.begin(); itr != water.end(); ++itr){
        for(auto itr_2 = suger.begin(); itr_2 != suger.end(); ++itr_2){
            int k = *itr / 100;
            k *= e;
            if(k >= *itr_2 && *itr + *itr_2 <= f){
                ans.push_back(make_pair(*itr, *itr_2));
            }
        }
    }

    double ans_q = 0;
    int flag = 0;
    for(int i = 0; i < ans.size(); i++){
        double k = ans[i].second * 100.0 / (ans[i].first + ans[i].second);
        if(k > ans_q){
            ans_q = k;
            flag = i;
        }
    }

    cout << ans[flag].first + ans[flag].second << " " << ans[flag].second << endl;

}

Measured memory_bytes: 3744
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;

int main(){
    int a;
    cin>>a;
    cout<<a+a*a+a*a*a;
}


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

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vii; //2次元配列
typedef vector<ll> vll;
typedef vector<string> vs;

struct point{
    ll x, y;
};

/*FUNCs=================================================*/



/*MAIN==================================================*/
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);   //cin cout 高速化

    int a, b, c, x, y;  cin >> a >> b >> c >> x >> y;
    int answer;
    if(a + b < 2 * c) answer += (a + b) * min(x, y);
    else answer += 2 * c * min(x, y);
    int res = max(x, y) - min(x, y);
    if(x < y) answer += min(b, 2 * c) * res;
    else answer += min(a, 2 * c) * res;
    cout << answer; 
}

Measured memory_bytes: 256
N=int(input())
s=input()
all=s.count('R')*s.count('G')*s.count('B')
a=0
for i in range(N):
  for j in range(1,(N-i)//2+1 ):
    if i + 2*j>=N:
      break
    if s[i]!=s[i+j] and s[i]!=s[i+2*j] and s[i+j] !=s[i+2*j]:
      a += 1
print(all-a)

Measured memory_bytes: 9196
main = do
 n <- readLn :: IO Int
 k <- readLn :: IO Int
 x1s <- (map read . words <$> getLine) :: IO [Int]
 let x2s = (k-) <$> x1s
 let m = 2 * sum(zipWith min x1s x2s)
 putStrLn $ show m

Measured memory_bytes: 1020
N = int(input())
L = [int(a) for a in input().split()]
cnt = 0
for i in range(0,N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            if L[i]!=L[j] and L[j]!=L[k] and L[k]!=L[i]:
                if (abs(L[i]-L[j])<L[k] and L[k]<L[i]+L[j]) or\
                (abs(L[j]-L[k])<L[i] and L[i]<L[j]+L[k]) or\
                (abs(L[k]-L[i])<L[j] and L[j]<L[k]+L[i]):
                    cnt += 1
print(cnt)

Measured memory_bytes: 9232
import Data.Maybe (fromJust)
import Data.List  (elemIndex)

main :: IO ()
main = do
  k <- readLn :: IO Int
  if k `mod` 2 == 0 || k `mod` 5 == 0
    then print (-1)
    else print $ succ $ fromJust $ elemIndex 0 $ iterate (\i -> (i * 10 + 7) `rem` k) (7 `rem` k)

Measured memory_bytes: 3944
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

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

        while(true) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            if(n == 0 && m == 0) break;

            int s = 0;
            for(int i = 0; i < 3; i++) {
                int num = sc.nextInt();
                for(int j = 0; j < num; j++) {
                    int x = sc.nextInt() - 1;
                    s += (int) Math.pow(3, x) * i;
                }
            }
            int g = 0;
            for(int i = 0; i < n; i++) {
                g *= 3;
                g += 1;
            }

            int[] cost = new int[(int) Math.pow(3, n)];
            cost[s] = 1;
            Deque<Integer> que = new ArrayDeque<>();
            que.add(s);

            while(!que.isEmpty()) {
                int i = que.poll();
                if(i == 0 || i == g * 2) break;
                if(cost[i] == m + 1) break;

                int top0 = -1;
                int top1 = -1;
                int top2 = -1;
                int tmp = i;
                for(int j = 0; j < n; j++) {
                    if(tmp % 3 == 0) top0 = j;
                    if(tmp % 3 == 1) top1 = j;
                    if(tmp % 3 == 2) top2 = j;
                    tmp /= 3;
                }

                if(top0 > top1) {
                    int ni = i + (int) Math.pow(3, top0);
                    if(cost[ni] == 0) {
                        cost[ni] = cost[i] + 1;
                        que.add(ni);
                    }
                }else if(top0 < top1) {
                    int ni = i - (int) Math.pow(3, top1);
                    if(cost[ni] == 0) {
                        cost[ni] = cost[i] + 1;
                        que.add(ni);
                    }
                }
                if(top1 > top2) {
                    int ni = i + (int) Math.pow(3, top1);
                    if(cost[ni] == 0) {
                        cost[ni] = cost[i] + 1;
                        que.add(ni);
                    }
                }else if(top1 < top2) {
                    int ni = i - (int) Math.pow(3, top2);
                    if(cost[ni] == 0) {
                        cost[ni] = cost[i] + 1;
                        que.add(ni);
                    }
                }
            }

            if(cost[0] > 0) System.out.println(cost[0] - 1);
            else if(cost[g * 2] > 0) System.out.println(cost[g * 2] - 1);
            else System.out.println(-1);
        }

        sc.close();
    }
}


Measured memory_bytes: 117296
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <iomanip>
#include <set>
using namespace std;

typedef long long ll;
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define SORT(s) sort((s).begin(),(s).end())

int main(){
    ll N,K; cin >> N >> K;
    if(N%K==0) cout << "0" << endl;
    else cout << "1" << endl;
}


Measured memory_bytes: 3624
if __name__ == '__main__':
    # a = int(input())
    # a, b = map(int, input().split())

    h = int(input())
    if h == 0:
        print("0")
        exit()
    monster = 1
    count = 0
    while h > 0:
        count += monster
        h //= 2
        monster *= 2
    print(count)



Measured memory_bytes: 38384
n, k = map(int, input().split())
a = list(map(int, input().split()))

s = [0]
for i in range(len(a)):
    s.append(s[-1] + a[i])

ss = []
for i in range(len(s)):
    ss.append((s[i] - i) % k)

# print(ss)

ans = 0
from collections import Counter
c = Counter(ss[1: min(k, len(ss))])
for i in range(len(ss)):
    # print(i, c)
    ans += c[ss[i]]

    if i + 1 < len(ss):
        c[ss[i + 1]] -= 1
    if i + k < len(ss):
        c[ss[i + k]] += 1

print(ans)


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

int main(int argc, char const *argv[]) {
    int w, h, x, y;
    cin >> w >> h >> x >> y;

    printf("%f %d\n", double(w)*double(h)/2, x*2 == w && y*2 == h);
    return 0;
}


Measured memory_bytes: 3756
#include <bits/stdc++.h>
using namespace std;
int main()
{
	char a[12];
	scanf("%s",&a);
	int N=strlen(a);
	long long s=0;
	for(int i=0;i<(1<<(N-1));i++)
	{
		long long m=0;
		m=a[0]-'0';
		for(int j=0;j<N-1;j++)
		{
			if(i&(1<<j))
			{
				s+=m;
				m =0;
			}
			m=m*10+a[j+1]-'0';
		}
		s+=m;
	}
	cout<<s<<endl;
	return 0;
}


Measured memory_bytes: 256
/*************************************************\
           In the name of almighty ALLAH
                 MD.Faysal Hasan
                Comilla Univesity
\*************************************************/

#include<bits/stdc++.h>
using namespace std;

#define     ikarus_101  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

typedef     long long             ll;
typedef     long double           ld;
typedef     unsigned long long    ull;
typedef     vector<ll>            vll;
typedef     pair<ll,ll>           pll;
typedef     vector<pll>           vpl;
typedef     map<ll,ll>            mll;
typedef     multiset<ll>          msl;
typedef     multimap<ll,ll>       Mll;
using pqboro=priority_queue<ll,vll,less<ll>>;
using pqchoto=priority_queue<ll,vll,greater<ll>>;

#define    all(str)       str.begin(),str.end()
#define    sajo(str)      sort(str.begin(),str.end())
#define    rev(str)       reverse(str.begin(),str.end())
#define    usajo(str)     sort(str.rbegin(),str.rend())
#define    vin(a)         for(auto &it : a) cin>>it
#define    vout(a)        for(auto it:a) cout<<it<<' ';cout<<nn
#define    pb             push_back
#define    eb             emplace_back
#define    mkp(x,y)       make_pair(x,y)
#define    F              first
#define    S              second
#define    yes            cout<<"YES"<<nn
#define    no             cout<<"NO"<<nn
#define    nn             "\n" ///endl
#define    rep(i,n)       for (i=0;i<n;++i )
#define    rep1(i,n)      for (i=1;i<=n;++i )

#define    min3(a,b,c)    min(a,min(b,c))
#define    max3(a,b,c)    max(a,max(b,c))
#define    sqr(x)         ((x)*(x))
#define    pi             2*acos(0.0)
#define    gcd(a,b)       __gcd(a,b)
#define    lcm(a,b)       (a/gcd(a,b))*b
#define    mem(a,b)       memset(a,b,sizeof (a))
#define    dec(x)         cout<<fixed<<setprecision(x)
#define    none(n)         __builtin_popcountll(n)

template < typename T > string toString ( T Number ) { stringstream ss ; ss << Number ; return ss.str() ; }
template < typename T > ll toll ( T str ) { stringstream ss ; ss << str ; ll num ; ss >> num ; return num ; }
ll power(ll n , ll k) { if(k == 0) return 1 ; if(k&1) return n*sqr(power(n,k/2)) ; else return sqr(power(n,k/2)); }

const   int  N   =   2e5+7;
const   int  M   =   1e9+7;
const   ll  inf  =   0x7f7f7f7f7f7f7f7f;

int main() {ikarus_101

    ll n,m,i,j,k,x;

    ll a,b,c;
    cin>>a>>b>>c;
    for(i=1;i<=b;++i)
    {
        if((a*i)%b==c) {
            yes;
            return 0;
        }
    }
    no;













    return 0;
}


Measured memory_bytes: 3620
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
// #define main int main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
#define stlice(from, to) substr(from, (to) - (from) + 1)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vd = vector<double>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vpii = vector<pii>;
using vvi = vector<vi>;
using vvb = vector<vb>;
using vvpii = vector<vpii>;
template<typename A> using fn = function<A>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
constexpr bool odd(const int &n) { return n & 1; }
constexpr bool even(const int &n) { return !odd(n); }
void solve();
main { solve(); return 0; }
// clang-format on

string f(string a, string b, int c) {
  if (!a.size()) return c ? string(1, c + '0') : "";
  int ia = a.back() - '0', ib = b.back() - '0';
  int s = ia + ib + c;
  c     = s / 10;
  a.pop_back(), b.pop_back();
  return f(a, b, c) + char(s % 10 + '0');
}

void solve() {
  int n;
  cin >> n;
  rep(_, n) {
    string a, b;
    cin >> a >> b;
    while (a.size() < b.size()) a = "0" + a;
    while (a.size() > b.size()) b = "0" + b;
    string x                      = f(a, b, 0);
    cout << (x.size() > 80 ? "overflow" : x) << endl;
  }
}

Measured memory_bytes: 2996
K, N = gets.split.map(&:to_i)
a = []
a = gets.split.map(&:to_i)

"自分の解答"
# ans, dis = 10e6
# N.times do |i|
#   dis = a[(i+N-1)%N] - a[i]
#   if dis <= 0
#     dis += K
#   end
#   ans = [ans, dis].min
# end
# puts ans

"想定解"
# A1 - AN のN個の区間の幅を生成
sep = []
N.times do |i|
  sep[i] = a[(i+1)%N] - a[i]
  if sep[i] <= 0
    sep[i] += K
  end
end
puts sep.inject(:+)-sep.max

Measured memory_bytes: 16972
from decimal import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
def li4():return [float(i) for i in input().rstrip('\n').split(' ')]

n,w = li()
l = []
for i in range(n):l.append(li())
l.sort()
d = defaultdict(int)
for i in range(10**5 + 10):d[i] = float('inf')
for i in l:

    for j in range(10 ** 5 + 10,0,-1):
        d[j + i[1]] = min(d[j + i[1]],d[j] + i[0])
    d[i[1]] = min(d[i[1]],i[0])
ans = 0
for i in range(10**5 + 10):
    if d[i] <= w:ans = i
print(ans)



Measured memory_bytes: 119380
#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; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size)
#define MOD 1000000007
const long long mod = 1e9+7;
typedef vector<long long> Vl;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<Vl> VVl;
typedef pair<int, int> PII;
typedef long long ll;

int main(){
    int a=0,b=0,c=0,d,n=0,x=0;
    VI m(5);
    string s,s1,s2;
    rep(i,5) cin >> m[i];
    cin >> n;
    if(abs(m[0] - m[4]) > n ){
         cout << ":(" << endl;
    }
    else cout << "Yay!" << endl;
    return 0;
} 

Measured memory_bytes: 384
#include <iostream>
#include<sstream>
#include<vector>
#include<iterator>
using namespace std;

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

	vector<vector<int>> A(2, vector<int>(N, 0));
	for(int i=0; i<2; i++)
		for(int j=0; j<N; j++)
			cin >> A[i][j];

	int sum = 0;
	vector<vector<int>> table(2, vector<int>(N, 0));
	for(int i=0; i<N; i++)
	{
		sum += A[0][i];
		table[0][i] = sum;
	}

	for(int i=0; i<N; i++){
		table[1][i] = max(table[1][i], table[0][i]+A[1][i]);
		if(i != 0)
			table[1][i] = max(table[1][i], table[1][i-1]+A[1][i]);
	}

	cout << table[1][N-1] << endl;

	return 0;
}


Measured memory_bytes: 256
#include<algorithm>
#include<bitset>
#include<cctype>
#include<cerrno>
#include<clocale>
#include<cmath>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<utility>
#include<vector>
#include<cwchar>
#include<cwctype>
using namespace std;
string st;
int sum,len;
signed main() {
    cin>>st;len=st.size();
    for(int i=0;i<len;i++)
        sum+=st[i]-'0';
    if(sum%9==0)
        puts("Yes");
    else
        puts("No");
}

Measured memory_bytes: 3484
#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#define sqr(x) (x)*(x)
using namespace std;
int n,m,i,j,k,l,r,mid,ans,num[305][305],now[305][305],mx[305];
bool check(int x)
{
	if (x<1) return 0;
	if (x>n) return 1;
	int i,j,k,s;
	vector<int> no;
	for (i=1;i<=n;i++)
	{
		for (j=1;j<=m;j++)
		{
			now[i][j]=1;
		}
		mx[i]=m;
	}		
	for (i=m;i;i--)
	{
		no.clear();
		for (j=1;j<=m;j++)
		{
			s=0;
			for (k=1;k<=n;k++)
			{
				if (mx[k]==num[k][j])
				{
					s++;
				}
			}
			if (s>x) no.push_back(j);
		}
		for (j=0;j<no.size();j++)
		{
			for (k=1;k<=n;k++)
			{
				now[k][num[k][no[j]]]=0;
			}
		}
		for (j=1;j<=n;j++)
		{
			for (k=m;k;k--)
			{
				if (now[j][k]) break;
			}
			mx[j]=k;
		}
	}
	for (i=1;i<=n;i++) if (mx[i]<=0) return 0;
	return 1;
}
int main()
{
	cin>>n>>m;
	for (i=1;i<=n;i++)
	{
		for (j=1;j<=m;j++)
		{
			int x;
			cin>>x;
			num[i][x]=m+1-j;
		}
	}
	l=0;r=n+1;ans=n;
	while (l<r)
	{
		mid=(l+r+1)/2;
		if (check(mid))
		{
			ans=mid;
			r=mid-1;
		}
		else l=mid;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int i,j,k;
int main(){
	int N=0,X=0;
	cin>>N>>X;
	for(i=0;i<=N;i++){
		for(j=0;j<=N;j++){
          k=N-i-j;
			if(k>=0){
		if(i*10000+j*5000+(N-i-j)*1000==X){
			cout<<i<<' '<<j<<' '<<k;
			return 0;
			
		}
		}
		
	}
}

	cout<<"-1 "<<"-1 "<<"-1";
	return 0;
}

Measured memory_bytes: 256
package main

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

func solve() {
	n, m := getInt(), getInt()

	// x: acするまでにかかる提出回数の期待値
	// y: 提出1回でかかる時間
	x := pow(2, m)
	y := m*1900 + (n-m)*100
	ans := x * y
	fmt.Fprintln(wr, ans)
}

func pow(a, b int) int {
	ret := 1
	for i := 0; i < b; i++ {
		ret *= a
	}
	return ret
}

// -----------------------------------------

const (
	inf = 1 << 60
	// mod = 1000000007
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wr = bufio.NewWriter(os.Stdout)
)

func main() {
	maxBufSize := int(1e8)
	sc.Buffer(make([]byte, 4096), maxBufSize)
	sc.Split(bufio.ScanWords)
	solve()
	wr.Flush()
}

func getInt() (ret int) {
	sc.Scan()
	ret, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return
}

func getIntSlice(n int) (ret []int) {
	ret = make([]int, n)
	for i := range ret {
		ret[i] = getInt()
	}
	return
}

func getString() (ret string) {
	sc.Scan()
	ret = sc.Text()
	return
}

func getRunes() (ret []rune) {
	ret = []rune(getString())
	return
}


Measured memory_bytes: 640
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>

#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define sz size()
#define pb push_back
#define mp make_pair
#define ALL(X) (X).begin(),(X).end()

using namespace std;

const int INF = 1000000000;
const double eps = 1e-8;

int dayid(string str) {
  int m = atoi(str.substr(0,2).c_str());
  int d = atoi(str.substr(3,2).c_str());
  return m * 40 + d;
}

int main(void) {
  while(1) {
    int n;
    cin>>n;
    if(!n)break;
    vector<int> times(1);
    map<int,int> pger;
    int gdsin = -1;
    REP(i,n){
      string day,time,io;
      int id;
      cin>>day>>time>>io>>id;
      int timet = atoi(time.substr(0,2).c_str()) * 60 + atoi(time.substr(3,2).c_str());
      if(id == 0) {
        if(io == "I") {
          gdsin = timet;
        }else{
          for(map<int,int>::iterator p = pger.begin(); p != pger.end(); ++p) {
            int in = max(p->second,gdsin);
            times[p->first] += timet - in;
          }
          gdsin = -1;
        }
      }else{
        if(io == "I") {
          if(id >= times.size()) {
            times.resize(id+1);
            //times[id] = 0;
          }
          pger.insert(make_pair(id,timet));
        }else{
          map<int,int>::iterator itr = pger.find(id);
          if(gdsin >= 0) {
            int in = max(itr->second,gdsin);
            times[id] += timet - in;
          }
          pger.erase(itr);
        }
      }
    }
    int m = 0;
    REP(i,times.size()) {
      m = max(m,times[i]);
    }
    cout << m <<endl;
  }
  return 0;
}

Measured memory_bytes: 1272
#include <stdio.h>
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <cmath>
#include <utility>
#include <iomanip>
#define input(a) cin >> a
#define input(a,b) cin >> a >> b
#define input(a,b,c) cin >> a >> b >> c
#define print(x) cout << x << endl
#define rep(a,n) for(int i = a; i < n; i++)
#define ll long long int
using namespace std;


int main(){
    int a,b,c,ans;
    input(a,b,c);
    ans = min(b/a, c);
    print(ans);
    
    return 0;
}


Measured memory_bytes: 256
s = gets.chomp
k = "keyence"
l = s.length - k.length

ans = "NO"

8.times do |i|
  if s[0..i] == k[0..i] && s[i + 1 + l..-1] == k[i + 1..-1]
    ans = "YES"
    break
  end
end

puts ans


Measured memory_bytes: 1788
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <math.h>
using namespace std;

#define ll long long int
#define MOD 1000000007
#define INF 1e9 + 1
#define fast ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define vi vector<int>
#define vl vector<long>
#define vll vector<long long>
#define pb push_back

char grid[1001][1001];


ll solve(int h, int w) {
	ll dp[h][w];
	for(int i = 0; i < h; i++) {
		for(int j = 0; j < w; j++) dp[i][j] = 0;
	}




		for(int i = 0; i < h; i++) {
			if(grid[i][0] == '#') {dp[i][0] = 0;break;}
			else dp[i][0] = 1;
		}
		for(int j = 0; j < w; j++) {
			if(grid[0][j] == '#') {dp[0][j] = 0;break;}
			else dp[0][j] = 1;
		}

		for(int i = 1; i < h; i++) {
			for(int j = 1; j < w; j++) {
				if(grid[i][j] == '#') dp[i][j] = 0;
				else {
					dp[i][j] = (dp[i-1][j] + dp[i][j-1])%MOD;
				}
			}
		}




		return (dp[h-1][w-1]) % MOD;
}


int main() {
	fast
	int t=1;
	// cin>>t;
	while(t--) {
		int h,w;
		cin>>h>>w;

		for(int i = 0; i < h; i++) {
			for(int j = 0; j < w; j++) {
				cin>>grid[i][j];
			}
		}

		cout<<solve(h,w)<<"\n";

	}
	return 0;
}


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

flag = False

for i in range(n-m+1):
    for j in range(n-m+1):
        cnt = 0
        for k in range(m):
            for l in range(m):
                if a[i+k][j+l] == b[k][l]:
                    cnt += 1
        if cnt == m**2:
            flag = True
            break
    if flag:
        break
print("Yes" if flag else "No")

Measured memory_bytes: 3064
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
typedef pair<int,int> Pint;
typedef pair<ll, ll> P;
//typedef pair<int, pair<int, int>> P;
//typedef tuple<int,int,int> T;
ll INFL = 1000000000000000010;//10^18 = 2^60
int INF = 2147483600;//10^9
ll MOD  = 1000000007;
vector<int> dy = {0,0,1,-1};
vector<int> dx = {1,-1,0,0};
ll gcd(ll a, ll b){//計算量はO(log(max(a,b))
    if(b == 0) return a;
    return gcd(b, a % b);
}
int main(void){
    ll N,M;
    cin >> N >> M;
    string S,T;
    cin >> S >> T;
    if(gcd(N, M) == 1){
        if(S.at(0) == T.at(0)){
            cout << N * M << endl;
        }else{
            cout << -1 << endl;
        }
    }else{
        bool l = 1;
        int sx = N / gcd(N, M);
        int tx = M / gcd(N, M);
        for(int i = 0; i < INF; i++){
            if(i * sx >= N || i * tx >= M)break;
            if(S.at(i * sx) != T.at(i * tx)){
                l = 0;
            }
        }
        if(l) cout << N / gcd(N, M) * M << endl;
        else cout << -1 << endl;
    }
}


Measured memory_bytes: 512
def gcd(a,b):
  n, m  = max(a, b), min(a, b)
  if n % m == 0:
    return m
  else:
    return gcd(m, n%m)

N, X = [int(item) for item in input().split()]
cities = [int(item) for item in input().split()]
if N == 1:
  print(abs(cities[0]-X))
  exit()

mod = gcd(abs(cities[0] - X), abs(cities[1] - X))
for i in range(2, N):
  mod = gcd(mod, abs(cities[i] - X))
print(mod)

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

using namespace std;

int main(){
    int a,b;
    cin>>a>>b;
    vector<int> n={0,1,3,1,2,1,2,1,1,2,1,2,1};
    if (n.at(a)==n.at(b)) {
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

//struct edge {int from, to, cost;};

constexpr double EPS = 1e-10;
//constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;
constexpr int MOD = 1'000'000'007;
//inline void modAdd(LL &l, LL &r) {l = (l + r) % MOD;}

template<class T> inline T sqr(T x) {return x*x;}

void solve() {
    int n;
    cin >> n;
    VS a(n);
    REP(i,0,n) cin >> a[i];
    REP(i,0,n) sort(all(a[i]));
    map<string,LL> m;
    REP(i,0,n) m[a[i]]++;
    LL ans = 0;
    for (auto &&p: m) {
        ans += p.second * (p.second - 1) / 2;
    }
    cout << ans << endl;
}

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

Measured memory_bytes: 18176