akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <functional>
#include <algorithm>
 
using namespace std;
 
#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define ALL(v) (v).begin(), (v).end()
#define LENGTHOF(x) (sizeof(x) / sizeof(*(x)))
#define AFILL(a, b) fill((int*)a, (int*)(a + LENGTHOF(a)), b)
#define SQ(x) ((x)*(x))
#define Mod(x, mod) (((x)+(mod)%(mod))
#define MP make_pair
#define PB push_back
#define Fi first
#define Se second
#define INF (1<<14)
#define EPS 1e-10
#define MOD 1000000007
 
typedef pair<int, int> pi;
typedef pair<int, pi> P;
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;
 
struct Edge{
  int to,d;
  Edge(int to, int d):to(to),d(d){}
};
 
int N,M,C, V;
vector<Edge>G[6001];
string city[6001];
char gs[6001];
short dist[2001][6001];
map<string,int>recity;
 
void dijkstra(int s){
  rep(i,C+1) fill(dist[i], dist[i]+V, INF);
  dist[C][s] = 0;
  priority_queue<P, vector<P>, greater<P> >q;
  q.push(MP(0, MP(C, s)));
 
  while(!q.empty()){
    P p = q.top(); q.pop();
    short cap = p.second.first, v = p.second.second, cost = p.first;
 
    if(dist[cap][v] < cost) continue;
    rep(i, G[v].size()){
      Edge e = G[v][i];
      if(e.d > cap) continue;
      short tar = max(cap-e.d, gs[e.to]*C);
      if(dist[tar][e.to] > dist[cap][v] + e.d){
    dist[tar][e.to] = dist[cap][v] + e.d;
    q.push(MP(dist[tar][e.to], MP(tar, e.to)));
      }
    }
  }
}
 
int main(){
  while(cin>>N>>M>>C, N||M||C){
 
    rep(i,3005) G[i].clear();
    memset(gs, 0, sizeof gs);
    recity.clear();
    C *= 10;
    V = 0;
    string src, dest;
    cin >> src >> dest;
 
    rep(i,N){
      string s1, s2; short d,u,v;
      cin >> s1 >> s2 >> d;
      if(recity.find(s1) == recity.end()){ recity[s1] = V; city[V++] = s1;}
      if(recity.find(s2) == recity.end()){ recity[s2] = V; city[V++] = s2;}
      u = recity[s1];
      v = recity[s2];
      G[u].push_back(Edge(v,d));
      G[v].push_back(Edge(u,d));
    }
 
    rep(i,M){
      string s;  cin >> s;
      gs[recity[s]] = 1;
    }
 
    dijkstra(recity[src]);
 
    short res = INF;
    rep(i, C+1) res = min(res, dist[i][recity[dest]]);
    cout <<(res==INF?-1:res)  << endl;
  }
  return 0;
}


Measured memory_bytes: 52600
using System.Linq;
using static System.Math;
using System;

public class hello
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine().Trim());
        string[] line = Console.ReadLine().Trim().Split(' ');
        var a = Array.ConvertAll(line, int.Parse);
        var r = new int[3];
        for (int i = 0; i < n; i++) r[a[i] % 3]++;
        var ans = getAns(r);
        Console.WriteLine(ans);
    }
    static int getAns(int[] r)
    {
        if (r[0] > 0 && r[1] == 0 && r[2] == 0) return 1;
        var ans1 = getAns1(r, 1);
        var ans2 = getAns1(r, 2);
        return Max(ans1, ans2);
    }
    static int getAns1(int[] r, int a)
    {
        if (r[a] == 0) return 0;
        var s = new int[3];
        for (int i = 0; i < 3; i++) s[i] = r[i];
        s[a]--;
        s[0] = 0;
        var wt = Min(s[1], s[2]);
        s[1] -= wt;
        s[2] -= wt;
        var ans = r.Sum() - s.Sum();
        if (a == 1 && s[1] > s[2]) ans++;
        if (a == 2 && s[2] > s[1]) ans++;
        if (s.Sum() > 0) ans++;
        return Min(ans, r.Sum());
    }
}



Measured memory_bytes: 48532
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int H,W;
  cin >> H >> W;
  vector<vector<int>> a(H,vector<int>(W));
  for (int i=0;i<H;i++){
    for (int j=0;j<W;j++){
      cin >> a[i][j];
    }
  }
  int ans=0;
  vector<vector<int>> v(H*W,vector<int>(4)); 
  for (int i=0;i<H;i++){
    for (int j=0;j<W;j++){
      if (a[i][j]%2==1){
        if (j!=W-1){
          v[ans][0]=i+1;
          v[ans][1]=j+1;
          v[ans][2]=i+1;
          v[ans][3]=j+2;
          a[i][j+1]++;
          ans++;
        }
        else {
          if (i!=H-1){
            v[ans][0]=i+1;
            v[ans][1]=j+1;
            v[ans][2]=i+2;
            v[ans][3]=j+1;
            a[i+1][j]++;
            ans++;
          }
        }
      }
    }
  }
  cout << ans << endl;
  for (int i=0;i<ans;i++){
    cout << v[i][0] << ' ' << v[i][1] << ' ' << v[i][2] << ' ' << v[i][3] << endl;
  }
}

Measured memory_bytes: 16768
#include <stdio.h>
long N(int x){
  return (long)(x+1)*(x+2)*(x+3)/6;
}

int main(){
  int n;
  while(~scanf("%d",&n)){
    if (n > 2000) n = 4000 - n;
    if (n < 1001) printf("%ld\n",N(n));
    else printf("%ld\n", N(n)-(N(2*(n-1000))-n+999)/2);
  }
  return 0;
}

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

int main() {
  int A, B;
  cin >> A >> B;
  
  if (B == 1) {
    cout << 0 << endl;
    return 0;
  }
  
  int sum = 0;
  int ans = 0;
  for (int i = 0; i < 310; i++) {
    if (i == 0) {
      sum += A; 
    } else {
      sum += A - 1;
    }
    ans ++;
    if (sum >= B) break;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#define MAX 1000000
int prime_count[MAX];
int main(void){
  int n = 0, i, j;

  for(i = 2; i < MAX; ++i){
    if(prime_count[i] != -1){
      for(j = i * 2; j < MAX; j += i){
        prime_count[j] = -1;
      }
      prime_count[i] = ++n;
    }else{
      prime_count[i] = n;
    }
  }

  while(scanf("%d", &n) != EOF){
    printf("%d\n", prime_count[n]);
  }
  return 0;
}

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

char Conv(char c , int key){

  char ls[]="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
  int indx;

  if(c>='a')indx = c-'a';
  else indx = 26+c-'A';

  if(indx < key)indx += 52;
  
  return ls[(indx-key)%52];

}

int main(){

  string eki;
  int n;
  int key[100];
  int indx;

  while(cin >> n , n){

    for(int i=0; i<n; i++)cin>>key[i];

    indx = 0;
    cin >> eki;

    for(int i=0; i<(int)eki.size(); i++){
      eki[i] = Conv(eki[i],key[indx]);
      indx = (indx+1)%n;
    }

    cout << eki << endl;

  }

  return 0;
}

Measured memory_bytes: 1200
fn main() {
    proconio::input! {
        a: i64,
        b: i64,
        h: i64,
        m: i64,
    }
    let hrad = h as f64 / 12.0 * 2.0 * std::f64::consts::PI
        + m as f64 / 60.0 / 12.0 * 2.0 * std::f64::consts::PI;
    let mrad = m as f64 / 60.0 * 2.0 * std::f64::consts::PI;
    let diffrad = (hrad - mrad).abs();
    let ans2 = (a * a + b * b) as f64 - 2.0 * a as f64 * b as f64 * diffrad.cos();
    let ans = ans2.sqrt();
    println!("{}", ans);
}


Measured memory_bytes: 3096
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;
int N;
int T[1<<17];
double A[1<<17];
main()
{
	cin>>N;
	A[0]=1;
	for(int i=0;i<N;i++)
	{
		int a;cin>>T[i]>>a;
		double x=(10.-a)/10;
		A[i+1]=A[i]*x;
	}
	int Q;cin>>Q;
	cout<<fixed<<setprecision(16);
	for(;Q--;)
	{
		int L,R;cin>>L>>R;
		L=upper_bound(T,T+N,L)-T;
		R=upper_bound(T,T+N,R)-T;
		cout<<1e9*A[R]/A[L]<<endl;
	}
}



Measured memory_bytes: 4468
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Scanner;
import java.util.AbstractMap.SimpleEntry;
import java.util.HashSet;
import java.util.Iterator;

class Main {

    static final int MOD = 1000000007;
    static int H;
    static int W;
    static int K;
    static char[][] base;
    static int[][] straw;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        H = sc.nextInt();
        W = sc.nextInt();
        K = sc.nextInt();
        base = new char[H][W];
        straw = new int[H][W];
        for (int y = 0; y < H; y++) {
            char[] str = sc.next().toCharArray();
            base[y] = str;
            for (int x = 0; x < W; x++) {
                straw[y][x] = str[x] == '#' ? -1 : 0;
            }
        }

        int iniY = 0;
        int iniX = 0;
        for (int block = 1; block <= K; block++) {

            init: for (int y = iniY; y < H; y++) {
                for (int x = 0; x < W; x++) {
                    if (straw[y][x] == -1) {
                        iniY = y;
                        iniX = x;
                        straw[iniY][iniX] = 0;
                        break init;
                    }
                }
            }
            while (iniX > 0 && straw[iniY][iniX - 1] == 0)
                iniX--;

            int ckx;
            for (ckx = iniX; ckx < W; ckx++) {
                if (straw[iniY][ckx] != 0) {
                    break;
                }
                //straw[iniY][ckx] = block;
            }            
            Arrays.fill(straw[iniY], iniX, ckx, block);
            expY: for (int y = iniY + 1; y < H; y++) {
                for (int x = iniX; x < ckx; x++) {
                    if (straw[y][x] != 0) {
                        break expY;
                    }
                }
                //System.out.println("expY"+ckx+" "+block);
                Arrays.fill(straw[y], iniX, ckx, block);
                // for (int x = iniX; x < ckx; x++) {
                // straw[y][x] = block;
                // }
            }
        }

        for (int y = H - 2; y >= 0; y--) {
            if (straw[y][0] == 0)
                straw[y] = straw[y + 1].clone();
        }

        for (int y = 0; y < H; y++) {
            String line = "";
            for (int x = 0; x < W; x++) {
                // System.out.print(String.format("%4d%c ",straw[y][x],base[y][x]));
                // System.out.print(straw[y][x] + " ");
                line += straw[y][x] + " ";
            }
            System.out.println(line);
        }
    }
}

Measured memory_bytes: 153872
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
ll INFLL = 1000000000000000010;//10^18 = 2^60
int INF = 2000000000;//10^9
ll MOD  = 998244353;
int N,M,R;
vector<vector<ll>> egde(210, vector<ll>(210, INF));
vector<vector<ll>> d(210, vector<ll>(210, INF));
void warshall_floyd(){
    for(int k = 0; k < N; k++){
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                d.at(i).at(j) = min(d.at(i).at(j), d.at(i).at(k) + d.at(k).at(j));
            }
        }
    }
}

vector<int> r(0);
vector<bool> vis(210);

bool all_visited(){
    bool res = 1;
    for(int i = 0; i < r.size(); i++){
        if(vis.at(r.at(i)) == 0){
            res = 0;
        }
    }
    return res;
}


ll solve(int now){
    if(all_visited()){
        return 0;
    }
    
    ll res = INFLL;
    for(int i = 0; i < r.size(); i++){
        if(vis.at(r.at(i))) continue;
        vis.at(r.at(i)) = 1;
        ll p;
        if(now == -1){
            p = solve(r.at(i));
        }else{
            p = solve(r.at(i)) + d.at(now).at(r.at(i));
        }
        res = min(res, p);
        vis.at(r.at(i)) = 0;
    }
    return res;
}

int main() {
    cin >> N >> M >> R;
    for(int i = 0; i < R; i++){
        int a;
        cin >> a;
        a--;
        r.push_back(a);
    }
    
    for(int i = 0; i < M; i++){
        int a,b;
        ll c;
        cin >> a >> b >> c;
        a--,b--;
        egde.at(a).at(b) = c;
        egde.at(b).at(a) = c;
        d.at(a).at(b) = c;
        d.at(b).at(a) = c;
    }
    
    for(int i = 0; i < N; i++){
        egde.at(i).at(i) = 0;
        d.at(i).at(i) = 0;
    }
    
    warshall_floyd();
    
    cout << solve(-1) << endl;
    
}

Measured memory_bytes: 896
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> P(N);
    for(int i = 0; i < N; i++){
        cin >> P[i];
    }

    UnionFind tree(N);

    for(int i = 0; i < M; i++) {
        int x, y;
        cin >> x >> y;
        tree.unite(x-1, y-1); // x-1の木とy-1の木を併合する
    }

    int cnt = 0;
    for(int i = 0; i < N; i++) {
        if (tree.same(i, P[i]-1)) { //iとP[i]-1が同じ木に属するなら，カウンタに1追加
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstdio>
#include <algorithm>
#include <map>
#include <queue>
#include <cstdlib>
#include <cstdio>
using namespace std;

#define rep(i, n) for(int (i) = (0); (i) < (n); (i++))
using ll = long long;

map<string, int> m;

int main() {
   string s, t, u;
    int a, b;
    cin >> s >> t >> a >> b >> u;

    m[s] = a;
    m[t] = b;

    m[u]--;
  
    cout << m.at(s) << " " << m.at(t) << endl;
}

Measured memory_bytes: 256
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2011

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
  int N;
  const int M = 60;
  while (scanf("%d", &N) != EOF && N) {
    bool R[40][M][M]; // i日目までにj番の人がkのマップを集めているか
    fill(&R[0][0][0], &R[0][0][0]+30*M*M, 0);
    vector<int> S[M];
    for (int i=0; i<N; i++) {
      int f;
      scanf("%d", &f);
      for (int j=0; j<f; j++) {
	int t;
	scanf("%d", &t);
	S[i].push_back(t);
      }
    }
    for (int i=0; i<N; i++) {
      R[0][i][i] = true;
    }
    for (int i=1; i<=30; i++) {
      for (int j=0; j<N; j++) {
	for (int k=0; k<N; k++) {
	  R[i][j][k] = R[i-1][j][k];
	}
      }
      vector<int> con; // i日目に会える人を格納
      // cerr << "DAY " << i << endl;
      for (int j=0; j<N; j++) {
	// cerr << (int) (find(S[j].begin(), S[j].end(), i) - S[j].begin()) << endl;
	if (find(S[j].begin(), S[j].end(), i) != S[j].end()) {
	  // cerr << j << " attends" << endl;
	  con.push_back(j);
	}
      }
      bool u[M];
      fill(u, u+M, false);
      for (unsigned int j=0; j<con.size(); j++) {
	for (int k=0; k<N; k++) {
	  if (R[i-1][con[j]][k]) u[k] = true;
	}
      }
      bool ans = true;
      for (int k=0; k<N; k++) {
	if (!u[k]) {
	  ans = false;
	  break;
	}
      }
      if (ans) {
	printf("%d\n", i);
	goto END;
      }
      for (unsigned int j=0; j<con.size(); j++) {
	for (int k=0; k<N; k++) {
	  R[i][con[j]][k] = u[k];
	}
      }
    }
    printf("%d\n", -1);
  END: continue;
  }
}

Measured memory_bytes: 1312
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ull h;
	cin>>h;
	ull init = 1;
	ull m = 0;
	while(h != 1){
		m = m + init;
		init *= 2;
		h/=2;
	}
	cout << m +init << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define range(i,a,n) for(ll i=(a);i<(n);i++)
#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI 3.1415926535897932384

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S sum(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *max_element(all(a));}

template<class T>void puta(T&&t){cout<<t<<endl;}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>void tf(bool b,S t,T f){if(b)puta(t);else puta(f);}
void OUT(bool b){tf(b,"YES","NO");}
void Out(bool b){tf(b,"Yes","No");}
void out(bool b){tf(b,"yes","no");}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1;for(auto s:t){os<<(a?"":" ")<<s;a=0;}return os;}
template<class S>auto&operator>>(istream&is,vector<S>&t){for(S&a:t)cin>>a;return is;}

int popcnt(int x){return __builtin_popcount(x);}
int popcnt(ll x){return __builtin_popcountll(x);}
int bsr(int x){return 31 - __builtin_clz(x);}
int bsr(ll x){return 63 - __builtin_clzll(x);}
int bsf(int x){return __builtin_ctz(x);}
int bsf(ll x){return __builtin_ctzll(x);}

/*他のライブラリを入れる場所*/

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	vi ans(n,INF);
	deque<pll> q;
	q.emplace_back(1,1);
	while(!q.empty()){
		ll num,cost;
		tie(num,cost)=q.front();
		q.pop_front();
		if(ans[num]!=INF)continue;
		ans[num]=cost;
		//puta(num,num%n,cost);
		if(ans[0]!=INF)break;
		if(ans[num*10%n]>cost){
			q.emplace_front(num*10%n,cost);
		}
		if(ans[(num+1)%n]>cost+1){
			q.emplace_back((num+1)%n,cost+1);
		}
	}
	puta(ans[0]);
	return 0;
}

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

int main()
{
  int n,q;
  for(;cin>>n>>q,n;)
    {
      int day[100];
      memset(day,0,sizeof(day));
      for(int i=0;i<n;i++)
	{
	  int m;
	  cin>>m;
	  for(;m--;)
	    {
	      int t;
	      cin>>t;
	      day[t]++;	   
	    }
	}
      int out=0;
      for(int i=1;i<100;i++)
	if(day[i]>=q && day[out]<day[i])
	      out=i;    
      cout<<out<<endl;
    }
}

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	int n,r;
	cin>>n>>r;
	if(n>=10)
	{
		cout<<r<<"\n";
	}
	else
	{
		int ans=r+100*(10-n);
		cout<<ans<<"\n";
	}
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApp14
{
    class Program
    {
        static void Main(string[] args)
        {
            var solver = new Solver();
            solver.Calc();
        }
    }

    public class Solver
    {

        public void Calc()
        {
            var ABC = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();

            Console.WriteLine(ABC.Distinct().Count() == 2 ? "Yes" : "No");


            //var NK = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();
            //var Ps = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();

            //var N = NK[0];
            //var K = NK[1];

            //var exPs = new double[1000];

            //for (var i = 0; i < 1000; i++)
            //{
            //    exPs[i] = (double)Enumerable.Range(1, i + 1).Sum() / (i + 1);
            //}


            //var sum = Ps.Where((x, i) => i < K).Sum();
            //var max = sum;
            //var maxIndent = 0;
            //for (var i = 0; i < N - K; i++)
            //{
            //    sum = sum - Ps[i] + Ps[i + K];
            //    if (max < sum)
            //    {
            //        max = sum;
            //        maxIndent = i + 1;
            //    }
            //}

            //var anser = Ps.Where((x, i) => maxIndent <= i && i < maxIndent + K).Select(x => exPs[x - 1]).Sum();

            //Console.WriteLine(anser);



            //Console.WriteLine(As.Distinct().Count() == As.Count() ? "YES" : "NO");

            //var SP = Console.ReadLine().Split();


            //var AB = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();

            //var U = Console.ReadLine();

            //var S = Console.ReadLine();

            //Console.WriteLine(new string('x', S.Length));


        }
    }
}

Measured memory_bytes: 13280
using System;
using System.Collections.Generic;
using System.Linq;

namespace ABC127
{
    class D
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split();
            long N = long.Parse(input[0]);
            long M = long.Parse(input[1]);
            long[] a = Console.ReadLine().Split().Select(long.Parse).OrderBy(x => x).ToArray();

            long[] B = new long[M];
            long[] C = new long[M];

            Dictionary<long, long> dict = new Dictionary<long, long>();

            for (long i = 0; i < N; i++)
            {
                if (!dict.ContainsKey(a[i])) dict.Add(a[i], 0);
                if (dict.ContainsKey(a[i])) dict[a[i]]++;

                /* この実装だとTLEになる */
                //if (!dict.ContainsKey(a[i])) dict.Add(a[i], a.Count(x => x == a[i]));
            }

            for (long i = 0; i < M; i++)
            {
                input = Console.ReadLine().Split();
                B[i] = long.Parse(input[0]);
                C[i] = long.Parse(input[1]);

                if (!dict.ContainsKey(C[i])) dict.Add(C[i], B[i]);
                else dict[C[i]] += B[i];
            }

            var dict2 = dict.OrderByDescending(x => x.Key);

            long res = 0;
            long count = 0;
            foreach (var item in dict2)
            {
                if (count + item.Value <= N) { res += item.Key * item.Value; count += item.Value; }
                else { res += item.Key * (N - count); Console.WriteLine(res); return; }
            }

            Console.WriteLine(res);
        }
    }
}


Measured memory_bytes: 43744
/*
 * =====================================================================================
 *
 *       Filename:  main.cpp
 *
 *    Description:  standard template
 *
 *        Version:  1.0
 *        Created:  30/07/2019 16:17:02
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Luigi Berducci (), berducci.1647887@studenti.uniroma1.it
 *        Company:  University of Rome La Sapienza
 *
 * =====================================================================================
 */

#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <string>

using namespace std;
int A, B;
int main ( int argc, char *argv[] ) {
    cin >> A >> B;
    int r1 = A+B;
    int r2 = A-B;
    int r3 = A*B;
    
    int res = max(r1, r2);
    cout << max(res, r3) << endl;
    return EXIT_SUCCESS;
}				/* ----------  end of function main  ---------- */


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

int main(){
  string s;
  cin >> s;
  int n = s.size();

  int ans = 0;
  int cnt = 0;
  for (int i = 0; i < n; i++)
  {
    if(s[i]=='A' || s[i]=='C' || s[i]=='G' || s[i]=='T') cnt++;
    else cnt = 0;
    ans = max(ans,cnt);
  }
  cout << ans << endl;  
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

namespace AtTest.ForYellow
{
    class ABC_163
    {
        static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(OpenStandardOutput()) { AutoFlush = false };
            SetOut(sw);

            Method(args);

            Out.Flush();
        }

        static void Method(string[] args)
        {
            int n = ReadInt();
            long[] array = ReadLongs();
            long[][] vals = new long[n][];
            for(int i = 0; i < n; i++)
            {
                vals[i] = new long[2] { array[i], i };
            }
            vals = vals.OrderBy(a => -a[0]).ToArray();

            long[,] dp = new long[n, n + 1];
            dp[0, 1] = vals[0][1] * vals[0][0];
            dp[0, 0] = (n - 1 - vals[0][1]) * vals[0][0];

            for(int i = 1; i < n; i++)
            {
                for(int j = 0; j <= i; j++)
                {
                    long left= dp[i - 1, j] + Abs(j-vals[i][1]) * vals[i][0];
                    long right = dp[i - 1, j] + Abs(n - 1 - (i - j) - vals[i][1]) * vals[i][0];
                    dp[i, j + 1] = Max(dp[i, j + 1], left);
                    dp[i, j] = Max(dp[i, j], right);
                }
            }

            long res = 0;
            for(int i = 0; i <= n; i++)
            {
                res = Max(res, dp[n - 1, i]);
            }
            WriteLine(res);
        }

        private static string Read() { return ReadLine(); }
        private static char[] ReadChars() { return Array.ConvertAll(Read().Split(), a => a[0]); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
    }
}


Measured memory_bytes: 51640
#include <stdio.h>
#include <stdlib.h>

int main (void) {
    int n;
    scanf("%d", &n);
    long int x, y, minz = 2000000000, maxz = 2, minw = 1000000000, maxw = -1000000000;
    for (int i = 0; i < n; i++) {
        scanf("%ld %ld", &x, &y);
        if (x + y < minz) {
            minz = x + y;
        }
        if (x + y > maxz) {
            maxz = x + y;
        }
        if (x - y < minw) {
            minw = x - y;
        }
        if (x - y > maxw) {
            maxw = x - y;
        }
    }

    if (maxz - minz > maxw - minw) {
        printf("%ld\n", maxz - minz);
    } else {
        printf("%ld\n", maxw - minw);
    }
    return 0;
}

Measured memory_bytes: 1700
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<deque>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
const int inf=1e9+7;
const ll INF=1LL<<60 ;
const ll mod=1e9+7 ;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<int, int> P;
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
#define debug(x)  cout << #x << " = " << (x) << endl;
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; }
#define int long long

void solve() {
	int m; cin >> m;
    vector<int> mp(10, 0);
    vector<int> d(m), c(m);
    rep(i, m) {
        cin >> d[i] >> c[i];
        mp[d[i]] += c[i];
    }
    int ans = 0;
  vector<int> mp2(10, 0);
    while(true) {
        bool check = false;
        for(int j = 0; j <= 9; ++j) {
            if(mp[j] >= 2) check = true;

            if(mp[j] == 0) continue;
            if(mp[j] % 2 == 1) {
                mp2[j] += 1;
            }
            if(j <= 4) {
                ans += mp[j] / 2;
                mp2[2 * j] += mp[j] / 2;
            }
            if(j >= 5) {
                ans += (mp[j] / 2) * 2;
                int k = 1 + (2 * j) % 10;
                mp2[k] += mp[j] / 2;
            }
        }
        swap(mp, mp2);
      for(int  j = 0; j <= 9; ++j) mp2[j] = 0;
        if(!check) break;
    }
    deque<int> deq;
    for(int j = 0; j <= 9; ++j) {
        if(mp[j] != 0) {
            deq.push_back(j);
        }
    }
    while(deq.size() > 1) {
        int a = deq.front();
        deq.pop_front();
        int b = deq.front();
        deq.pop_front();
        int w = a + b;
        if(w <= 9) {
            deq.push_front(w);
            ans ++;
        } else {
            int w2 = w - 10;
            ans ++;
            deq.push_front(w2);
            deq.push_front(1);
        }
    }

    cout << ans << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//init();
	solve();
	//cout << "finish" << endl;
    return 0;
}

Measured memory_bytes: 3328
# must have sum even. This only happens for x,y both even or both odd.
# N even, so N*(N-1)/2 pairs of them (not counting order). Same for M.
N, M = map(int, input().split())
num_N = N*(N-1)//2
num_M = M*(M-1)//2
print(num_N+num_M)

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

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

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

int gcd(int a,int b){
	if(b>0){
		return gcd(b, a % b);
	}else{
		return a;
	}
}

ll N,M;


int main()
{
	cin >> N>>M;
	if(N>M){
		int tmp = M;
		M = N;
		N = tmp;
	}
	if (N == 1 && M != 1)
	{
		cout << M - 2 << endl;
	}else if(N==1&&M==1){
		cout << 1 << endl;
	}else{
		ll ans = (N - 2) * (M - 2);
		cout <<ans<< endl;
	}

	return 0;
}

Measured memory_bytes: 256
val MOD = 1000000000+ 7

fun main(args : Array<String>) {
    val S = readLine()!!


    val dpAny = LongArray(S.length + 1)
    val dpA = LongArray(S.length + 1)
    val dpAB = LongArray(S.length + 1)
    val dpABC = LongArray(S.length + 1)

    dpAny.fill(0)
    dpAny[0] = 1
    dpA.fill(0)
    dpAB.fill(0)
    dpABC.fill(0)

    (1..S.length).forEach {i ->
        val s = S[i - 1]
        dpAny[i] = (dpAny[i-1]) % MOD
        if (s == 'A') {
            dpA[i] = (dpA[i - 1] + dpAny[i-1]) % MOD
        } else {
            dpA[i] = dpA[i - 1] % MOD
        }

        if (s == 'B') {
            dpAB[i] = (dpAB[i - 1] + dpA[i - 1]) % MOD
        } else {
            dpAB[i] = dpAB[i - 1] % MOD
        }

        if (s == 'C') {
            dpABC[i] = (dpABC[i - 1] + dpAB[i - 1]) % MOD
        } else {
            dpABC[i] = dpABC[i - 1] % MOD
        }

        if (s == '?') {
            dpAny[i] = (3 * dpAny[i-1]) % MOD
            dpA[i] = (3 * dpA[i-1] + dpAny[i-1]) % MOD
            dpAB[i] = (3 * dpAB[i-1] + dpA[i - 1]) % MOD
            dpABC[i] = (3 * dpABC[i-1] + dpAB[i - 1]) % MOD
        }
    }

    println(dpABC[S.length])
}

Measured memory_bytes: 41696
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
#include <stdio.h>
#include <ctype.h>
using namespace std;
#define pie 3.141592653589793238462643383279
#define mod 1000000007
#define INF 1145141919364364
#define int long long
#define all(vec) vec.begin(),vec.end()
#define P pair<int,int>
#define S second
#define F first
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
bool prime(int x) {
	for (int i = 2; i <= sqrt(x); i++) {
		if (x%i == 0)return false;
	}
	return true;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod;
}

int n;
string s[200000];
vector<P> cnt;
vector<string> ans;

signed main() {
	cin >> n;
	for (int i = 0; i < n; i++)cin >> s[i];
	sort(s, s + n);
	int k = 1;
	for (int i = 1; i < n; i++) {
		if (s[i - 1] != s[i]) {
			cnt.push_back({ k,i - 1 });
			k = 1;
		}
		else k++;
	}
	cnt.push_back({ k,n - 1 });
	sort(all(cnt));
	reverse(all(cnt));
	int ma = cnt[0].first;
	for (int i = 0; i < (int)cnt.size(); i++) {
		if (cnt[i].first == ma)ans.push_back(s[cnt[i].second]);
		else break;
	}
	sort(all(ans));
	for (int i = 0; i < (int)ans.size(); i++)cout << ans[i] << endl;
}

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

#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0, a1, a2, a3, a4, x, ...) x
#define dump_1(x1) cerr << #x1 << ": " << x1 << endl
#define dump_2(x1, x2) \
  cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << endl
#define dump_3(x1, x2, x3)                                                \
  cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \
       << x3 << endl
#define dump_4(x1, x2, x3, x4)                                            \
  cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \
       << x3 << ", " #x4 << ": " << x4 << endl
#define dump_5(x1, x2, x3, x4, x5)                                        \
  cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \
       << x3 << ", " #x4 << ": " << x4 << ", " #x5 << ": " << x5 << endl
#define dump(...) \
  CHOOSE((__VA_ARGS__, dump_5, dump_4, dump_3, dump_2, dump_1, ~))(__VA_ARGS__)
#define check(s) cerr << s << endl

#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 unique(v) v.erase(unique(v.begin(), v.end()), v.end());
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)

using namespace std;

using ll = long long;

const long long MOD = 2;

vector<int> dx = {0, 1, 0, -1};
vector<int> dy = {1, 0, -1, 0};

const ll LINF = 2e18;
const int INF = 1e9;

void solve(ll N, ll P, std::vector<ll> A) {
  vector<vector<ll>> dp(N, vector<ll>(2));

  if (A.at(0) % 2 == 0) {
    dp.at(0) = {2, 0};
  } else {
    dp.at(0) = {1, 1};
  }

  for (int i = 1; i < N; i++) {
    if (A.at(i) % 2 == 0) {
      dp.at(i).at(0) = dp.at(i - 1).at(0) * 2;
      dp.at(i).at(1) = dp.at(i - 1).at(1) * 2;
    } else {
      dp.at(i).at(0) = dp.at(i - 1).at(0) + dp.at(i - 1).at(1);
      dp.at(i).at(1) = dp.at(i - 1).at(1) + dp.at(i - 1).at(0);
    }
  }

  cout << dp.at(N - 1).at(P) << endl;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  ll N;
  scanf("%lld", &N);
  ll P;
  scanf("%lld", &P);
  std::vector<ll> A(N);
  for (int i = 0; i < N; i++) {
    scanf("%lld", &A[i]);
  }
  solve(N, P, std::move(A));
  return 0;
}


Measured memory_bytes: 3660
import numpy as np
K, N = map(int, input().split())
A = list(map(int, input().split()))
A = np.array(A)
ma = 0
for i in range(N-1):
  if A[i+1] - A[i] > ma:
    ma = A[i+1] -A[i]
if K -(A[N-1] -A[0]) > ma:
  ma = K -(A[N-1] -A[0])
print(K -ma)


Measured memory_bytes: 42844
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define LL long long
using namespace std;

LL n, x, f[55], g[55];

LL solve(LL l, LL r, LL x)
{
	if(r-l+1>=f[x]) return g[x];
	LL temp=0;
	if(r) r--;
	if(x && r) temp+=solve(1, r, x-1);
	if(x && r>=f[x-1])
	{
		r-=f[x-1];
		if(r) r--, temp++;
		if(r) temp+=solve(1, r, x-1);
	}
	return temp;
}

int main()
{
	f[0]=g[0]=1;
	for(int i=1; i<=50; i++)
	{
		f[i]=f[i-1]*2+3;
		g[i]=g[i-1]*2+1;
	}
	scanf("%lld%lld", &n, &x);
	printf("%lld\n", solve(1, x, n));
	return 0;
}

Measured memory_bytes: 128
package main

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

var sc = bufio.NewScanner(os.Stdin)

func main() {
	scanInit()

	n := nextInt()
	_ = nextInt()
	s := make([]string, n)

	for i := 0; i < n; i++ {
		s[i] = nextStr()
	}

	sort.Strings(s)

	for i := 0; i < n; i++ {
		fmt.Printf(s[i])
	}
}

// ---- readfunc
func scanInit() {
	const cap = 200 * 1024 // Default=64
	var buf = make([]byte, cap)
	sc.Buffer(buf, cap)
	sc.Split(bufio.ScanWords)
	return
}
func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}
func nextStr() string {
	sc.Scan()
	return sc.Text()
}


Measured memory_bytes: 1760
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
using vi = vector<int64_t>;
using vvi = vector<vi>;
int64_t INF = 1000000007;
// int64_t INF = 9223372036854775807;

int main() {
    // fasten cin
    cin.tie(0);
    ios::sync_with_stdio(false);
    // implement
    int64_t x;
    cin >> x;
    string res = "0";
    rep(i,1000){
        if(100*i<=x && x<=105*i){
            res = "1";
            break;
        }
    }
    cout << res << endl;
}

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

const int maxn = 11, maxq = 51;
struct query { int a, b, c, d; } q[maxq];
int n, m, k, a[maxn];
int best = 0;
void bt(int i, int mn){
	if (i == n+1){
		int cand = 0;
		for(int j = 0; j<k; j++){
			query&t = q[j];
			cand += t.d * (a[t.b] - a[t.a] == t.c);
		}
		best = max(best, cand);
		return;
	}
	for(int j = mn; j<=m; j++){
		a[i] = j;
		bt(i+1, j);
		a[i] = -1;
	}


}

int main(){
	cin >> n >> m >> k;
	for(int i = 0; i<k; i++){
		cin >> q[i].a >> q[i].b >> q[i].c >> q[i].d;
	}
	bt(1, 1);
	cout << best << endl;
	return 0;
}

Measured memory_bytes: 3608
#include <cstdio>
#include <stack>
#include <algorithm>

using namespace std;

const int V_MAX = 30;
const int INF = 10000000;

int h, w;
int n;
char c[10][11];

const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
const char D[] = {'R', 'D', 'L', 'U'};

stack<int> ans;

int dfs(int x, int y, int d)
{
    c[x][y] = '.';

    bool ko = true;
    for (int i = 0; ko && i < h; ++i) {
        for (int j = 0; ko && j < w; ++j) {
            if (c[i][j] == 'o')
                ko = false;
        }
    }
    if (ko)
        return 4;

    //printf("  dfs(%2d, %2d, %c)\n", x, y, D[d]);
    for (int i = 0; i < 4; ++i) {
        if ((d + 2) % 4 == i)
            continue;

        int nx = x + dx[i];
        int ny = y + dy[i];
        for (;;) {
            if (nx < 0 || h <= nx || ny < 0 || w <= ny)
                break;
            if (c[nx][ny] == 'o') {
                int ret = dfs(nx, ny, i);
                if (ret != -1) {
                    ans.push(i);
                    return i;
                }
                break;
            }
            nx += dx[i];
            ny += dy[i];
        }
    }

    c[x][y] = 'o';

    return -1;
}

int main()
{
    scanf("%d %d", &h, &w);
    for (int i = 0; i < h; ++i)
        scanf(" %s", c[i]);

    int sx, sy, sd;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (c[i][j] == 'U' || c[i][j] == 'D' || c[i][j] == 'L' || c[i][j] == 'R') {
                sx = i;
                sy = j;
                if (c[i][j] == 'U')
                    sd = 3;
                else if (c[i][j] == 'D')
                    sd = 1;
                else if (c[i][j] == 'L')
                    sd = 2;
                else if (c[i][j] == 'R')
                    sd = 0;
            }
        }
    }

    dfs(sx, sy, sd);
    while (!ans.empty()) {
        printf("%c", D[ans.top()]);
        ans.pop();
    }
    puts("");

    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <functional>

using namespace std;

int main() {
    string s, t;

    cin >> s >> t;

    sort(s.begin(), s.end());
    sort(t.begin(), t.end(), greater<char>());

    if(s < t)   cout << "Yes" << endl;
    else        cout << "No"  << endl;

    return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
 
//template
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(a);i>(b);i--)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll; typedef pair<ll, ll> P;
template<class T> inline bool chmax(T& a, T b) { if(a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if(a > b) { a = b; return 1; } return 0; }
template<typename A,size_t N,typename T>void Fill(A(&array)[N],const T &val){fill((T*)array, (T*)(array+N), val);}
const int inf = INT_MAX / 2; const ll INF = LLONG_MAX / 2;
//template end

int mod = 1e9+7;
struct Mint {
  int val;
  Mint inv() const {
    int tmp, a = val, b = mod, x = 1, y = 0;
    while(b) tmp = a / b, a -= tmp * b, swap(a, b), x -= tmp * y, swap(x, y);
    return Mint(x);
  }
public:
  Mint() :val(0) {}
  Mint(ll x) :val(x >= 0 ? x % mod : x % mod + mod) {}
  int mtoi() { return this->val; }
  Mint pow(ll t) { Mint res = 1,b = *this; while(t){if(t&1)res *= b;b *= b;t >>= 1;}return res; }
  Mint& operator+=(const Mint& x) { if ((val += x.val) >= mod) val -= mod; return *this; }
  Mint& operator-=(const Mint& x) { if ((val += mod - x.val) >= mod) val -= mod; return *this; }
  Mint& operator*=(const Mint& x) { val = (ll)val * x.val % mod; return *this; }
  Mint& operator/=(const Mint& x) { return *this *= x.inv(); }
  bool operator==(const Mint& x) const { return val == x.val; }
  bool operator!=(const Mint& x) const { return val != x.val; }
  bool operator<(const Mint& x) const { return val < x.val; }
  bool operator<=(const Mint& x) const { return val <= x.val; }
  bool operator>(const Mint& x) const { return val > x.val; }
  bool operator>=(const Mint& x) const { return val >= x.val; }
  Mint operator+(const Mint& x) const { return Mint(*this) += x; }
  Mint operator-(const Mint& x) const { return Mint(*this) -= x; }
  Mint operator*(const Mint& x) const { return Mint(*this) *= x; }
  Mint operator/(const Mint& x) const { return Mint(*this) /= x; }
};
struct factorial {
  vector<Mint> Fact, Finv;
public:
  factorial(int maxx) {
    Fact.resize(maxx+1,Mint(1)),Finv.resize(maxx+1); rep(i,0,maxx)Fact[i+1]=Fact[i]*Mint(i+1);
    Finv[maxx]=Mint(1)/Fact[maxx]; rrep(i,maxx,0)Finv[i-1]=Finv[i]*Mint(i);
  }
  Mint fact(int n,bool inv) { if(inv) return Finv[n]; else return Fact[n]; }
  Mint nPr(int n,int r) { if(n<0||n<r||r<0) return Mint(0); else return Fact[n]*Finv[n-r]; }
  Mint nCr(int n,int r) { if(n<0||n<r||r<0) return Mint(0); else return Fact[n]*Finv[r]*Finv[n-r]; }
};
vector<vector<int>> g;
Mint dp[100010][2]; bool used[100010]={};
void dfs(int v){
  used[v]=true;
  for(int p:g[v])if(!used[p]){
    dfs(p);
    dp[v][0]*=(dp[p][0]+dp[p][1]);
    dp[v][1]*=dp[p][0];
  }
}


int main(){
  int n; scanf("%d",&n);
  g.resize(n);
  rep(i,0,n-1){
    int u,v; scanf("%d%d",&u,&v); u--; v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  Fill(dp,1); dfs(0);
  dp[0][0]+=dp[0][1];
  printf("%d\n",dp[0][0].mtoi());
  return 0;
}


Measured memory_bytes: 10752
module Main where
--import Debug.Trace
import Data.List
import Data.Char
import Data.Array
import Data.Maybe
import Data.Ord
import Control.Monad

solve :: [Int] -> [[Int]]
solve = iter [] where
    iter al []        = [al]
    iter [] xl@(x:xs) = iter [x] xs
    iter al xl@(x:xs) =(al++xl):iter (insertX x al) xs where
        insertX x [] = [x]
        insertX x al@(a:as)
            | a > x = x:al
            | otherwise = a:insertX x as
 
readLine:: IO [Int]
readLine = fmap (map read . words) getLine

main :: IO() 
main = do
    n <- readLn :: IO Int
    l <- readLine
    mapM_ putStrLn $ map (\y -> init (concatMap (\x-> show x ++ " ") y)) (solve l)



Measured memory_bytes: 4084
#include<stdio.h>
#include<string.h>

int main(){
    int i;
    int lose=0;
    char hoshi[15];
    scanf("%s",&hoshi);
    for(i=0;i<strlen(hoshi);i++){
        if(hoshi[i]=='x')lose+=1;
    }

    if(lose>=8){
        printf("NO\n");
    }else{
        printf("YES\n");
    }
    return 0;
}

Measured memory_bytes: 128
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reg(i,a,b) for(int i=(a);i<=(b);i++)
#define irep(i,n) for(int i=((int)(n))-1;i>=0;i--)
#define ireg(i,a,b) for(int i=(b);i>=(a);i--)
typedef long long int lli;
typedef pair<int,int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX

int n,m;
char s[200][200];


int dp[200000];

int pow(int p,int q){
  int res=1;
  rep(i,q)res*=p;
  return res;
}

int main(void){

  for(;;){
    scanf("%d%d",&n,&m);
    if(n==0)break;
    rep(i,m)scanf("%s",s[i]);
    memset(dp,0,sizeof(dp));

    int nl=pow(3,n);
    int ans=100;

    //printf("nl .. %d\n",nl);
    
    rep(i,nl){
      int nb[15]={},ii=i;
      rep(j,n){
	nb[j]=ii%3;
	ii/=3;
      }

      /*
      rep(j,n){
	printf("%d ",nb[j]);
      }
      printf("\n");*/

      int ns=0;
      rep(j,m){
	bool ok=true;
	rep(k,n){
	  if(nb[k]!=2 && (((char)nb[k])+'0')!=s[j][k])ok=false;
	}
	if(ok)ns++;
      }
      if(ns<=1){
	if(ns==1)dp[i]=0;
	else dp[i]=1000;
	//printf("%d\n",i);
	continue;
      }

      
      int nmin=100;
      int tb[15]={};
      rep(j,n){
	tb[j]=nb[j];
	//printf("%d ",tb[j]);
      }
      //printf(" ..tb\n");
      
      rep(j,n){
	if(tb[j]!=2)continue;
	
	int ne=-100;
	rep(p,2){
	  tb[j]=p;

	  int t=0,bas=1;
	  rep(k,n){
	    t+=tb[k]*bas;
	    bas*=3;
	  }
	  //if(i==8)printf("tot .. %d\n",t);
	  ne=max(ne,dp[t]);
	  
	  tb[j]=nb[j];
	}
	nmin = min(ne,nmin);
	//printf("doing %d %d %d\n", i,j,ne);
      }
      
      dp[i]=nmin+1;

      //printf("do .. %d %d %d \n",i,ns,dp[i]);
      
      
    }
    printf("%d\n",dp[pow(3,n)-1]);
  }
  return 0;
}

Measured memory_bytes: 1852
# -*- coding: utf-8 -*-
n,k = list(map(int,input().split()))
a = list(map(int,input().split()))

from collections import defaultdict
d = defaultdict(int)
for i in a:
    d[i]+=1
not_change_cnt = 0
for i,v in enumerate(sorted(d.values(),reverse=True)):
    if i+1 > k:
        break
    else:
        not_change_cnt+=v
print(n-not_change_cnt)


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

int main() 
{
	int n, m;
	cin >> n >> m;
	int x[m];
	for (int i = 0; i < m; i++)
		cin >> x[i];
	if (n >= m) {cout << 0; return 0;}
	
	sort(x, x + m);
	
	int diff[m];
	for (int i = 0; i < m - 1; i++)
		diff[i] = x[i + 1] - x[i];
	sort(diff, diff + m - 1, greater<int>());
	
	long long sum = x[m - 1] - x[0];
	for (int i = 0; i < n - 1; i++)
		sum -= diff[i];
	
	cout << sum;
}

Measured memory_bytes: 1024