akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int h, w, n;
vector<vector<bool>> mp;
vector<pair<int,int>> f;

int calc(pair<int,int> start, pair<int,int> end){
	vector<vector<int>> hi(w, vector<int>(h, 1145141919));
	priority_queue<pair<int, pair<int,int>>, vector<pair<int, pair<int,int>>>, greater<pair<int, pair<int,int>>>> q;
	q.push(make_pair(0, start));
	while(q.size()){
		int c = q.top().first;
		pair<int,int> p = q.top().second;
		q.pop();
		if(p == end) return c;
		int x = p.first;
		int y = p.second;
		for(int dx = -1; dx <= 1; dx++){
			for(int dy = -1; dy <= 1; dy++){
				if((!!dx ^ !!dy) && 0 <= x+dx && x+dx < w && 0 <= y+dy && y+dy < h && !mp[x+dx][y+dy] && hi[x+dx][y+dy] > c+1){
					hi[x+dx][y+dy] = c+1;
					q.push(make_pair(c+1, make_pair(x+dx, y+dy)));
				}
			}
		}
	}
	return -1;
}

int main(){
	cin >> h >> w >> n;
	mp.assign(w, vector<bool>(h, false));
	f.assign(n+1, make_pair(0, 0));
	for(int y = 0; y < h; y++){
		for(int x = 0; x < w; x++){
			char a;
			cin >> a;
			if(a == 'X') mp[x][y] = true;
			if(a == 'S') f[0] = make_pair(x, y);
			if('1' <= a && a <= '9') f[a - '0'] = make_pair(x, y);
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; i++){
		ans += calc(f[i-1], f[i]);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 6980
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int func(const void *a, const void *b){
  return strcmp((const char*)a, (const char*)b);
}
int main(void){
  char str[100][200] = {{0}};
  int n, l;
  scanf("%d %d", &n, &l);getchar();
  for(int i = 0; i < n; i++){
    fgets(str[i], 200, stdin);
    str[i][l] = 0;
  }
  qsort(&str[0][0], n, sizeof(char) * 200, func);
  for(int i = 0; i < n; i++){
    printf("%s", str[i]);
  }
  return 0;
}

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


 
int main(){
 long long N;
  cin>>N;
  if(N%2!=0){
    cout<<0<<endl;
    return 0;
  }
  int64_t ans=0;
  N/=2;
  while(N>0){
  N/=5;
  ans+=N;
}
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define ll long long
#define lld long double
#define MOD 998244353
#define inf 1000000000
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
ll power(ll x,ll y, ll md=inf){ll res = 1;x%=md;while(y){if(y&1)res = (res*x)%md;x *= x; if(x>=md) x %= md; y >>= 1;}return res;}
 
using namespace std;

#define endl '\n'
#define int ll


signed main() {
	fast;

	int n;
	cin>>n;
	vector<pair<pii,char>> v(n);

	for(int i=0;i<n;i++) cin>>v[i].f.f>>v[i].f.s>>v[i].s;

	map<int,set<int>> mn1, mn2;
	
	int f = 1;
	int ans = inf;

	for(int i=0;i<n;i++) {
		if(v[i].s=='U') {
			mn1[v[i].f.f].insert(v[i].f.s);
		}

		if(v[i].s=='R') {
			mn2[v[i].f.s].insert(v[i].f.f);
		}
	}

	for(int i=0;i<n;i++) {
		if(v[i].s=='D') {
			auto it = mn1[v[i].f.f].lower_bound(v[i].f.s);
			if(it!=mn1[v[i].f.f].begin()) {
				it--;
				f = 0;
				ans = min(ans, 5*(v[i].f.s-*it));
			}
		}
		if(v[i].s=='L') {
			auto it = mn2[v[i].f.s].lower_bound(v[i].f.f);
			if(it!=mn2[v[i].f.s].begin()) {
				it--;
				f = 0;
				ans = min(ans, 5*(v[i].f.f-*it));
			}
		}
	}

	sort(all(v));

	map<int,int> st[4];
	for(int i=0;i<n;i++) {
		int x = v[i].f.f + v[i].f.s;

		if(v[i].s=='U' && st[3].count(x)) {
			f = 0;
			ans = min(ans, 10*abs(v[i].f.f-st[3][x]));
		}
		if(v[i].s=='L' && st[1].count(x)) {
			f = 0;
			ans = min(ans, 10*abs(v[i].f.f-st[1][x]));
		}

		if(v[i].s=='U') st[0][x] = v[i].f.f;
		if(v[i].s=='D') st[1][x] = v[i].f.f;
		if(v[i].s=='L') st[2][x] = v[i].f.f;
		if(v[i].s=='R') st[3][x] = v[i].f.f;
	}

	map<int,int> dt[4];
	for(int i=0;i<n;i++) {
		int x = v[i].f.f - v[i].f.s;

		if(v[i].s=='D' && dt[3].count(x)) {
			f = 0;
			ans = min(ans, 10*abs(v[i].f.f-dt[3][x]));
		}
		if(v[i].s=='L' && dt[0].count(x)) {
			f = 0;
			ans = min(ans, 10*abs(v[i].f.f-dt[0][x]));
		}

		if(v[i].s=='U') dt[0][x] = v[i].f.f;
		if(v[i].s=='D') dt[1][x] = v[i].f.f;
		if(v[i].s=='L') dt[2][x] = v[i].f.f;
		if(v[i].s=='R') dt[3][x] = v[i].f.f;
	}

	if(f) cout<<"SAFE";
	else cout<<ans;
}

Measured memory_bytes: 51044
#include <iostream>
#include <math.h>
#include <numeric>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <tuple>
#include <functional>

#define PI 3.14159265359
#define INF 1e9
#define LINF 1e18
#define rep(i,n) for(long long  i = 0; i < n; i++)
#define rep2(i,a,n) for(long long  i = a; i < n; i++)
#define in(a) cin >> a
#define out(a) cout << a << endl
typedef long long ll;

using namespace std;

int main() 
{
    string s; cin >> s;

    if(s == "SUN") { cout << 7 << endl; }
    if(s == "MON") { cout << 6 << endl; }
    if(s == "TUE") { cout << 5 << endl; }
    if(s == "WED") { cout << 4 << endl; }
    if(s == "THU") { cout << 3 << endl; }
    if(s == "FRI") { cout << 2 << endl; }
    if(s == "SAT") { cout << 1 << endl; }

    return 0;
}



Measured memory_bytes: 256
#include <stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h> 
typedef  long long ll;
#define length 3000 //10万
#define kw_len 10+2
int compare(const int*a,const int *b){
    if(*a<*b)
      return -1;
    else if(*a>*b)
      return 1;
    return 0;
}
 
ll nCr(int n,int r){
  ll val;
  int i;
  if(r==0)return 1;
  for(i=0;i<r;i++){
		val *= (n-i);
		val /= (i+1);
	}
  return val;
}
 
ll nPr(int n,int r){
  ll val=1;
  int i;
  for(i=0;i<r;i++){
    val *= (n-i);
  }
  return val;
}
/*
qsort(array,length,sizeof(int),(int(*)(const int*, const int*))compare);
使う時これをコピペ
*/


int main(){
    int array[length]; 
    int N,i,j,m;
    ll sum=0,K,v=0,sumtemp=0,mod=0,temp,ttt,bk;
    scanf("%d%lld",&N,&K);
    for(i=0;i<N;i++){
      scanf("%d",array+i);
    }
  bk =(K*(K-1)/2)%1000000007;
    for(i=0;i<N;i++){
        temp=0;
        ttt=0;
        for(j=0;j<N;j++){    //全部でデカいの何個あるか
            if(*(array+i)>*(array+j)){
            temp++;}
        }
        sumtemp= (sumtemp+(temp*bk))%1000000007;
        for(m=i+1;m<N;m++){
            if(m>=N)break;
            if(*(array+i)>*(array+m)){
                ttt++;
            }
        }
        sum= (sum + ttt*K)%1000000007;
        
    }
        sum= sum+sumtemp;
    printf("%lld",sum%1000000007);
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>	// require sort next_permutation count __gcd reverse etc.
#include <cstdlib>	// require abs exit atof atoi 
#include <cstdio>		// require scanf printf
#include <functional>
#include <numeric>	// require accumulate
#include <cmath>		// require fabs
#include <climits>
#include <limits>
#include <cfloat>
#include <iomanip>	// require setw
#include <sstream>	// require stringstream 
#include <cstring>	// require memset
#include <cctype>		// require tolower, toupper
#include <fstream>	// require freopen
#include <ctime>		// require srand
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(A) A.begin(), A.end()

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

int main()
{
	int N;
	while (scanf ("%d", &N ), N  ){
		vector<P> v; v.clear();
		rep (i, N ){
			int h1, m1, s1, h2, m2, s2;
			scanf ("%d:%d:%d %d:%d:%d", &h1, &m1, &s1, &h2, &m2, &s2 );
			v.push_back (P (h1*60*60 + m1*60 + s1, 1 ) );
			v.push_back (P (h2*60*60 + m2*60 + s2,-1 ) );
		} // end rep
		sort (ALL (v ) );

		int res = 0;
		int cur = 0;
		rep (i, v.size() ){
			cur += v[i].second;
			res = max (res, cur );
		} // end rep
		cout << res << endl;
	} // end while
		
	return 0;
}

Measured memory_bytes: 1460
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)n; i++)
#define all(x) (x).begin(),(x).end()
typedef long long int ll;
using namespace std;
int main()
{
  int n, m;
  cin >> n >> m;
  ////////////////////////////////////
  if(n >= m){
    cout << 0 << endl;
    return 0;
  }
  ////////////////////////////////////
  vector<int > x(m, 0);
  int sum = 0;
  REP(i, m){
    cin >> x[i];
  }
  sort(all(x));
  // cout << "x" << endl;
  // REP(i, m){cout << x[i] << endl;}
  vector<int > sub(m - 1, 0);
  REP(i, m - 1){
    sub[i] = x[i + 1] - x[i];
    sum += sub[i];
  }
  // cout << "sub" << endl;
  // REP(i, m - 1){cout << sub[i] << endl;}
  int ans = x[m - 1] - x[0];
  // cout <<"sum = " << ans<<" "<<sum << endl;
  ////////////////////////////////////
  sort(all(sub));
  // REP(i, m - 1){cout << sub[i] << endl;}
  ////////////////////////////////////
  REP(i, n - 1){
    ans -= sub[m - 2 - i];
  }
  // cout << endl;
  cout << ans << endl;
}


Measured memory_bytes: 1024
// Aizu Vol-2 0225: Kobutanukitsuneko
// 2017.8.7

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char *gets();
char buf[50];

#define MAX 26

/* UNION-FIND library */
int p[MAX], rank[MAX];

void make_set(int x) { p[x] = x, rank[x] = 0; }
void link(int x, int y) {
	if (rank[x] > rank[y]) p[y] = x;
	else { p[x] = y; if (rank[x] == rank[y]) rank[y] = rank[y] + 1;	}
}
int find_set(int x) { if (x != p[x]) p[x] = find_set(p[x]);	return p[x]; }
void union_set(int x, int y) { link(find_set(x), find_set(y)); }

int s[MAX], e[MAX];

int main()
{
	int n, a, b, k;
	
	while (1) {
		gets(buf), n = atoi(buf);
		if (n == 0) break;
		memset(s, 0, sizeof(s)), memset(e, 0, sizeof(e));
		memset(p, 0, sizeof(p)), memset(rank, 0, sizeof(rank));
		while (n-- > 0) {
			gets(buf);
			a = buf[0] - 'a', b = buf[strlen(buf)-1] - 'a';
			if (!s[a] && !e[a]) make_set(a);
			if (!s[b] && !e[b]) make_set(b);
			if (find_set(a) != find_set(b)) union_set(a, b);
			s[a]++, e[b]++;
		}

		for (k = -1, n = 0; n < 26; n++) {
			if (s[n] || e[n]) {
				if (k < 0) k = find_set(n);
				else if (find_set(n) != k) break;
			}
			if (s[n] != e[n]) break;
		}
		puts(n >= 26 ? "OK" : "NG");
	}
	return 0;
}

Measured memory_bytes: 520
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin>>N;
  int s=0;
  for(int i=1;i<N+1;i+=2){
    int a=sqrt(i);
    int t=0;
    for(int j=1;j<a+1;j++){
      if(i%j==0) t++;
    }
    if(t==4) s++;
  }
  cout<<s<<endl;
}


Measured memory_bytes: 384
def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n): return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
import itertools
# import math
# import networkx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop

n=n0()
X=[]
for i in range(n):
    a=n0()
    x=n3(a)
    X.append(x)

ite=list(itertools.product([0,1],repeat=n))
ite.sort(key=lambda x:sum(x),reverse=True)

s=0
for line in ite[:-1]:
    ans=[i for i in line]
    flag=True
#     print(line)
    for i in range(n):
        if line[i]==1:
            for a,b in X[i]:
#                 print(ans[a-1],a,b)
                if ans[a-1]!=b:
                    flag=False
                    break
            if flag==False:
                break
    if flag==True:
        for j in range(n):
            if ans[j]==1:
                if line[j]!=1:
                    break
        else:
            s=sum(line)
            break
print(s)
            

Measured memory_bytes: 9460
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

//void substring_dfs(vector < int, int > substring){
    
//}
int di[4] = {-1,0,1,0};
int dj[4] = {0,1,0,-1};

int main(int argc, const char * argv[]) {
    // insert code here...
    
    int n,m;
    cin >> n >> m;
    
    vector < string > map;
    
    for(int i = 0; i < n; i++){
        string temp;
        cin >> temp;
        map.push_back(temp);
    }
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            
            if(map[i][j] == '#'){
                bool hantei_d = false;
                for(int k = 0; k < 4; k++){
                    int x = i + di[k];
                    int y = j + dj[k];
                    if (x >= 0 && y >= 0 && x < n && y < m && map[x][y] == '#') {
                        hantei_d = true;
                        break;
                    }
                }
                if(hantei_d == false) {
                    cout << "No" << endl;
                    return 0;
                }
            }
            
        }
    }
    
    cout << "Yes" << endl;
    
    return 0;
}


Measured memory_bytes: 256
using System;
public class Program
{
    public static void Main()
    {
        string s = Console.ReadLine();
        string ans = "";
        for (int i = 0; i < s.Length; i++)
        {
            if (i % 2 == 0)
            {
                ans += s[i];
            }
        }
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 34772
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
//#pragma GCC optimize("Ofast")
//#define _GLIBCXX_DEBUG
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
//#define int ll
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define floatprec(dig) fixed << setprecision(dig)
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int;
#define invar(typ, var) typ var; cin >> var;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
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;}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX / 2;
const ll LLINF = 1LL<<60;
constexpr ll MOD = 1000000007;
const double EPS = 1e-9;

void solve(int modu, int C, int N, vvi& c, vvi& D) {
  //変えた後の色がkのときの違和感合計
  //かつ，別のあまりなら，色が異ならないといけない
  
}

signed main(void) {
  cin.tie(0); ios::sync_with_stdio(false);
  
  int N, C;
  cin >> N >> C;
  
  vvi D(C, vi(C));
  
  rep(i, C) {
    rep(j, C) {
      cin >> D[i][j];
    }
  }
  
  vvi c(N, vi(N));
  rep(i, N) {
    rep(j, N) {
      cin >> c[i][j];
      c[i][j]--;
    }
  }
  vector<vector<ll>> dsum(3, vector<ll>(C));
  
  //modごと，各色に変えたときのコスト合計を算出
  //別に+1しなくてもmodは成立
  rep(i, N) {
    rep(j, N) {
      int orgcol = c[i][j];
      int m = (i + j) % 3;
      rep(k, C) {
        dsum[m][k] += (ll)D[orgcol][k];
      }
    }
  }
  
  int cc[3];
  int mval = INF;
  for(cc[0]=0; cc[0]<C; cc[0]++) {
    for(cc[1]=0; cc[1]<C; cc[1]++) {
      if(cc[0] == cc[1]) continue;
      for(cc[2]=0; cc[2]<C; cc[2]++) {
        if(cc[0] == cc[2] || cc[1] == cc[2]) continue;
        
        int iwa = 0;
        rep(it, 3) iwa += dsum[it][cc[it]];
        chmin(mval, iwa);
      }
    }
  }
  
  fin(mval);
  
}

Measured memory_bytes: 1280
import java.util.*;

class Main{

    void solve(){
        Scanner sc = new Scanner(System.in);

        int num = sc.nextInt();
        while(num-->0){
            int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
            if(a==0 && b==0 && c==0) break;

            double[] set = new double[3];
            set[0] = a; set[1] = b; set[2] = c;
            Arrays.sort(set);

            boolean boo = false;
            if(set[0]==set[1] && set[0]*Math.sqrt(2)==set[2]) boo = true;
            if(set[0]*Math.sqrt(3)==set[1] && set[0]*2==set[2]) boo = true;

            for(int i=1; i<=set[2]; i++){
                if(set[0]/i==3 && set[1]/i==4 && set[2]/i==5) boo = true;
                if(set[0]/i==5 && set[1]/i==12 && set[2]/i==13) boo = true;
            }
            if(boo) System.out.println("YES");
            else System.out.println("NO");
        }
    }

    public static void main(String[] args){
        new Main().solve();
    }
}

Measured memory_bytes: 23376
//Quick Sort
#include <iostream>
#include <climits>

using namespace std;

struct Card {
    char suit;
    int num;
};

int partition(Card A[], int p, int r) {
    int x = A[r].num;
    int i = p - 1;
    for(int j = p; j < r; j++) {
        if(x >= A[j].num) {
            i++;
            swap(A[i], A[j]);
        }
    }
    swap(A[i + 1], A[r]);
    return i + 1;
}

void quickSort(Card A[], int p, int r) {
    if(p >= r) return;
    int x = partition(A, p, r);
    quickSort(A, p, x-1);
    quickSort(A, x+1, r);
}

void merge(Card A[], int left, int mid, int right) {
    int n1 = mid - left;
    int n2 = right - mid;
    Card L[n1 + 1], R[n2 + 1];
    for (int i = 0; i < n1; i++) L[i] = A[left + i];
    for (int i = 0; i < n2; i++) R[i] = A[mid + i];
    L[n1].num = INT_MAX;
    R[n2].num = INT_MAX;
    int l = 0, r = 0;
    for (int i = left; i < right; i++) {
        if (L[l].num <= R[r].num) A[i] = L[l++];
        else A[i] = R[r++];
    }
}

void mergeSort(Card A[], int left, int right) {
    if(right > 1 + left) {
        int mid = (left + right) / 2;
        mergeSort(A, left, mid);
        mergeSort(A, mid, right);
        merge(A, left, mid, right);
    }
}

bool isStable(Card A1[], Card A2[], int n) {
    for(int i = 0; i < n; i++) {
        if(A1[i].suit != A2[i].suit) return false;
    }
    return true;
}


int main() {
    int n;
    cin >> n;
    Card A1[n], A2[n];
    for(int i = 0; i < n; i++) cin >> A1[i].suit >> A1[i].num;
    for(int i = 0; i < n; i++) {A2[i].suit = A1[i].suit; A2[i].num = A1[i].num;}

    quickSort(A1, 0, n - 1);
    mergeSort(A2, 0, n);

    if(isStable(A1, A2, n)) cout << "Stable" << endl;
    else cout << "Not stable" << endl;

    for(int i = 0; i < n; i++) {
        cout << A1[i].suit << " " << A1[i].num << endl;
    }
}


Measured memory_bytes: 5368
import numpy as np

h,w = map(int, input().split())
a = [list(input()) for _ in range(h)]

b = []
for i in a:
    if set(i) != {'.'}:
        b.append(i)
b = np.array(b)
b = b.T

c = []
for i in b:
    if set(i) != {'.'}:
        c.append(i)
c = np.array(c)
c = c.T

for i in c:
    print(''.join(i))

Measured memory_bytes: 12536
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1LL<<60;

ll solve() {
    ll N, M, b, c;
    cin >> N >> M;
    vector<ll> A(M);
    vector<int> k(M);
    for ( int i = 0; i < M; i++ ) {
        cin >> A[i] >> b;
        for ( int j = 0; j < b; j++ ) {
            cin >> c;
            c--;
            k[i] |= (1<<c);
        }
    }

    int NN = 1<<N;
    vector<ll> dp(NN, INF), dpp(NN);
    dp[0] = 0;
    for ( int i = 0; i < M; i++ ) {
        copy(dp.begin(), dp.end(), dpp.begin());
        for ( int j = 0; j < NN; j++ ) {
            if ( dpp[j] != INF ) {
                int kk = j | k[i];
                dp[kk] = min(dp[kk], dpp[j] + A[i]);
            }
        }
    }
    if ( dp[NN-1] == INF ) return -1;
    else return dp[NN-1];
}

int main() {
    auto ans = solve();
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 384
def check():
    N, M = map(int, input().split())
    edge = [[] for _ in range(N)]
    for i in range(M):
        a,b = map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    for v in edge[0]:
        if N-1 in edge[v]:
            return 'POSSIBLE'
    return 'IMPOSSIBLE'
print(check())

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

using namespace std;

template <typename T, typename = typename std::enable_if<
                          std::is_integral<T>::value, T>::type>
map<T, int> prime_factorize(T n) {
  map<T, int> cnts{};
  if (n == 1) {
    return cnts;
  }

  T a = 2;
  while (n >= a * a) {
    int cnt = 0;
    while (n % a == 0) {
      n /= a;
      cnt++;
    }

    if (cnt > 0) {
      cnts[a] = cnt;
    }

    a++;
  }

  if (n != 1) {
    cnts[n] = 1;
  }

  return cnts;
}

int main(int argc, const char *argv[]) {
  int n;
  cin >> n;

  map<int, int> factors;
  factors[1] = 1;
  for (int i = 2; i <= n; ++i) {
    auto f = prime_factorize(i);
    for (auto &p : f) {
      factors[p.first] += p.second;
    }
  }

  int cnt_3, cnt_5, cnt_15, cnt_25, cnt_75;
  cnt_3 = cnt_5 = cnt_15 = cnt_25 = cnt_75 = 0;
  for (auto p : factors) {
    p.second++;
    if (p.second >= 3) {
      cnt_3++;
    }

    if (p.second >= 5) {
      cnt_5++;
    }

    if (p.second >= 15) {
      cnt_15++;
    }

    if (p.second >= 25) {
      cnt_25++;
    }

    if (p.second >= 75) {
      cnt_75++;
    }
  }

  int ans = 0;
  // A_1 ^ 3  * A_2 ^ 5 * A_3 ^ 5
  ans += max(0, cnt_3 - 2) * max(0, cnt_5 * (cnt_5 - 1) / 2);

  // A_1 ^ 25 * A_2 ^ 3
  ans += max(0, cnt_3 - 1) * cnt_25;

  // A_1 ^ 15 * A_2 ^ 5
  ans += max(0, cnt_5 - 1) * cnt_15;

  // A_1 ^ 75
  ans += cnt_75;

  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int n,m,h=0,mi,a,b=0,i;
  scanf("%d %d %d",&n,&m,&b);
  for(i=1;i<n;i++){
    scanf("%d",&a);
    if(a+b>=m&&h==0){
      h=1;
      mi=i;
    }
    b=a;
  }
  if(h==0){
    printf("Impossible\n");
    return 0;
  }
  printf("Possible\n");
  for(i=1;i<mi;i++)printf("%d\n",i);
  for(i=n;i>mi;i--)printf("%d\n",i-1);
  return 0;
}

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

using namespace std;

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

typedef long long ll;
typedef long double ld;

const int Inf = 1e9;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(0);
    int h, n;
    cin >> h >> n;
    vector<int> dp(h + 1, Inf);
    dp[0] = 0;
    rep (i, n) {
        int a, b;
        cin >> a >> b;
        rep (j, h) {
            int next = min(j + a, h);
            dp[next] = min(dp[next], dp[j] + b);
        }
    }
    cout << dp[h] << endl;
    
    return 0;
}



Measured memory_bytes: 892
import java.util.*;


public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        Map<Integer, Integer> map = new HashMap<>();
        for (int n = 0; n < N; n += 1) {
            int K = sc.nextInt();
            for (int k = 0; k < K; k += 1) {
                int a = sc.nextInt();
                if (!map.containsKey(a)) {
                    map.put(a, 1);
                } else {
                    map.put(a, map.get(a) + 1);
                }
            }
        }

        Set<Integer> keys = map.keySet();
        int n = 0;
        for (int a : keys) {
            if (map.get(a) == N) {
                n += 1;
            }
        }
        System.out.println(n);
    }
}


Measured memory_bytes: 23764
#include<iostream>
#include<iomanip>
#include<algorithm>

using namespace std;

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

int main(){
    int X,Y,Z;
    cin >> X >> Y >> Z;
    cout << (X-Z)/(Y+Z);
}

Measured memory_bytes: 256
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#include"debug_deque.hpp"
#define vector DebugDeque
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(prints) FUNC(printe) FUNC(printw) FUNC(printew) FUNC(printb) FUNC(printd) FUNC(printde);
#endif
template <class S, class T>
istream& operator >> (istream& in, pair<S, T>& p){ in >> p.first >> p.second; return in; }
template <class T>
istream& operator >> (istream& in, vector<T>& v){ for(auto& e : v){ in >> e; } return in; }

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    vector<int> as(n); cin >> as;
    for(auto& a : as){
        printb(a);
    }
    ll ans = 0;
    int cnt = 1, num = as[0], beg = 0;
    for(int i = 1; i < n; i++){
        if(!(num & as[i])){
            cnt++;
            num |= as[i];
        }else{
            // ans += 1ll * cnt * (cnt + 1) / 2;
            prints(ans);
            // cnt = 1;
            while(num & as[i]){
                num ^= as[beg++];
                // ans += cnt;
                cnt--;
            }
            num |= as[i];
        }
        ans += i - beg + 1;
        printd(ans);
    }
    // ans += n - beg;
    ans++;
    // ans += 1ll * cnt * (cnt + 1) / 2;
    cout << ans << '\n';
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define vec_input(v) for(auto it=v.begin();it!=v.end();it++){cin>>*it;}
#define vec_output(v) for(auto it=v.begin();it!=v.end();it++){if(it!=v.begin())cout<<" ";cout<<*it;}cout<<endl;
#define vec_debug(v) for(auto it=v.begin();it!=v.end();it++){cerr<<*it<<" ";}cerr<<endl;
#define yn(ans) cout<<(ans?"Yes":"No")<<endl
#define YN(ans) cout<<(ans?"YES":"NO")<<endl
#define umap unordered_map
#define uset unordered_set
using namespace std;
using ll = long long;
template <typename T>T digitsum(T n);
template <typename T>bool isPrime(T n);
template <typename T>vector<pair<T, T>> prime_factor(T n);
long long int intpow(long long int,long long int);
template <typename T>T intlog(T);
long long int combination(long long int,long long int);
long long int arith_sum1(long long int,long long int,long long int);
long long int arith_sum2(long long int,long long int,long long int);
long long int series_sum(long long int);

int main(){
    vector<int> vec(200000,0);
    int n,k,x;
    cin>>n>>k;
    rep(i,n){
        cin>>x;
        vec[x]++;
    }
    sort(rall(vec));
    ll ans=0;
    rep(i,vec.size()){
        if(i<k)continue;
        if(vec[i]==0)break;
        ans+=(ll)vec[i];
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3848
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#define int long long
using namespace std;

int n;
int a[100000];
int k[99999];

signed main() {
	int i;
	
	cin >> n;
	for (i = 0; i < n; i++) cin >> a[i];
	for (i = 0; i < n - 1; i++) k[i] = a[i + 1] - a[i];
	
	//操作回数Xを求める
	int asum = 0;
	for (i = 0; i < n; i++) asum += a[i];
	if (asum % (n * (n + 1) / 2) != 0) { cout << "NO" << endl; return 0; }
	int X = asum / (n * (n + 1) / 2);
	
	for (i = 0; i < n - 1; i++) k[i] -= X;
	
	//k[i] == -Nの倍数となっているか？
	int cnt = 0;
	for (i = 0; i < n - 1; i++) {
		if (k[i] > 0 || (-k[i]) % n != 0) {
			cout << "NO" << endl;
			return 0;
		}
		cnt += (-k[i]) / n;
	}
	
	if (cnt <= X) { cout << "YES" << endl; }
	else { cout << "NO" << endl; }
	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9+7;
const ll MOD2 = 998244353;
const ll INF = 1e18;

int main(){
    ll N, K;
    cin >> N >> K;
    ll i = 1;
    set<ll> s;
    while(N/i > N/(i+1)){
        s.insert(N/i);
        i++;
    }
    rep3(j, N/i, 1){
        s.insert(j);
    }
    set<ll>::iterator ite;;
    ite = s.begin();
    ll n = s.size();
    ll dp[K][n], a[n], num[n];
    rep(i, n){
        a[i] = *ite;
        ite++;
    }
    num[0] = 1;
    rep2(i, 1, n-1){
        num[i] = a[i]-a[i-1];
    }
    rep(i, n){
        dp[0][i] = num[i];
    }
    rep2(i, 1, K-1){
        ll S[n];
        S[n-1] = dp[i-1][0];
        rep3(j, n-2, 0) S[j] = (S[j+1]+dp[i-1][n-1-j])%MOD;
        ll pos = 0;
        rep(j, n){
            while(a[j]*a[n-1-pos] > N) pos++;
            dp[i][j] = (num[j]*S[pos])%MOD;
        }
    }
    ll ans = 0;
    rep(i, n){
        ans += dp[K-1][i];
        ans %= MOD;
    }
    cout << ans << endl;
}

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0; i<n; i++){
        cin >> a[i];
    }

    sort(a.begin(), a.end());
    cout << a[n-1] - a[0] << endl;
    return 0;
}

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

struct stu
{
	int a,b;
}s[1000];
struct point
{
	int x,y;
}w[1000];
inline int dis(stu a,point b)
{
	return abs(a.a-b.x)+abs(a.b-b.y);
}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>s[i].a>>s[i].b;
	for(int i=1;i<=m;i++)cin>>w[i].x>>w[i].y;
	for(int i=1;i<=n;i++)
	{
		int num,maxn=1e9;
		for(int j=1;j<=m;j++)
		{
			if(dis(s[i],w[j])<maxn)
			{
				num=j;
				maxn=dis(s[i],w[j]);
			}
		}
		cout<<num<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
using namespace std;
int a[100005];
int main() {
    int n;
    scanf("%d",&n);
    for (int i=1; i<=n; i++) {
        scanf("%d",&a[i]);
    }
    long long Max=2,Min=2;
    for(int i=n;i>=1;i--)
    {
        if(Min%a[i]!=0)
        Min=Min/a[i]*a[i]+a[i];
        Max=Max/a[i]*a[i]+a[i]-1;
        
    }
    if(Min>Max)
    {
        puts("-1");
        return 0;
    }
    printf("%lld %lld\n", Min, Max);
    return 0;
}

Measured memory_bytes: 640
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static final int INF = Integer.MAX_VALUE / 2 - 1;
	public static final int MAX = 20;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int[] req_bit = new int[MAX];
		int[] amounts = new int[MAX];
		int[] DP = new int[1 << MAX];
		
		while(true){
			final int n = sc.nextInt();
			final int U = sc.nextInt();
			
			if(n == 0 && U == 0){
				break;
			}
			
			for(int i = 0; i < n; i++){
				amounts[i] = sc.nextInt();
				
				final int k = sc.nextInt();
				int bit = 0;
				for(int j = 0; j < k; j++){
					bit |= 1 << (sc.nextInt());
				}
				
				req_bit[i] = bit;
			}
			
			Arrays.fill(DP, INF);
			DP[0] = 0;
			
			final int bit_size = 1 << n;
			for(int bit = 0; bit < bit_size; bit++){
				if(DP[bit] >= U){
					continue;
				}
				
				for(int next = 0; next < n; next++){
					if((bit & (1 << next)) != 0){
						continue;
					}else if((bit & (req_bit[next])) != req_bit[next]){
						continue;
					}
					
					DP[bit | (1 << next)] = Math.min(DP[bit | (1 << next)], DP[bit] + amounts[next]);
				}
			}
			/*
			for(int i = 0; i < bit_size; i++){
				System.out.println(Integer.toBinaryString(i) + "\t : " + DP[i]);
			}
			*/
			int min = INF;
			for(int i = 0; i < bit_size; i++){
				if(DP[i] >= U && DP[i] < INF){
					//System.out.println(Integer.toBinaryString(i) + "\t : " + DP[i]);
					min = Math.min(min, Integer.bitCount(i));
				}
			}
			
			System.out.println(min);
		}
		
	}

}

Measured memory_bytes: 29964
#!/usr/bin/env python
"""NOMURA プログラミングコンテスト 2020: C - Folia
https://atcoder.jp/contests/nomura2020/tasks/nomura2020_c
"""


def main():
    N = int(input())
    As = list(map(int, input().split()))

    leaves_count = sum(As)
    node_count = 1
    ans = 0
    for i, a in enumerate(As):
        leaves_count -= a
        next_node_count = min(leaves_count, (node_count - a) * 2)
        if next_node_count < 0:
            ans = -1
            break
        ans += node_count
        node_count = next_node_count

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 19956
#include<bits/stdc++.h>
#define int long long
#define iris 998244353
#define matsuri pair<int,int>
using namespace std;

int arr[200010],id[200010];
int ll[200010],ans[200010];
int bit[200010],p;
set<int> s;

void mdf(int a,int k)
{
	while(a<=p)
	{
		bit[a]=min(bit[a], k);
		a+=a&(-a);
	}
}

int qry(int a)
{
	int res=1e9;
	while(a)
	{
		res=min(res, bit[a]);
		a-=a&(-a);
	}
	return res;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n,i,a,b,l,o;
	cin>>n;
	p=n;
	for(i=1;i<=n;i++)
	{
		cin>>a>>b;
		arr[a]=b;
		id[a]=i;
		bit[i]=1e9;
		s.insert(i);
	}
	for(i=1;i<=n;i++)
	{
		o=qry(arr[i]);
		if(o==1e9)
			o=i;
		ll[i]=o;
		mdf(arr[i], i);
	}
	for(i=1;i<=n;i++)
	{
		while(*s.lower_bound(ll[i])!=i)
		{
			s.erase(s.lower_bound(ll[i]));
		}
	}
	l=1;
	for(int r:s)
	{
		for(i=l;i<=r;i++)
		{
			ans[id[i]]=r-l+1;
		}
		l=r+1;
	}
	for(i=1;i<=n;i++)
	{
		cout<<ans[i]<<'\n';
	}
	
	return 0;
}

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

#define rep(i,m,n) for(int i = (m); i < (n); i++)
#define rrep(i,m,n) for(int i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define print2(x,y) cout << (x) << " " << (y) << endl;
#define printa(x,n) for(int i = 0; i < n; i++){ cout << (x[i]); if(i!=n-1) cout << " ";} cout << endl;
#define printp(x,n) for(int i = 0; i < n; i++){ cout << "(" << x[i].first << ", " << x[i].second << ") "; } cout << endl;
#define INF (1e18)
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
typedef pair<ll, ll> lpair;
int mp_a[1000010] = {}, mp_b[1000010] = {};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N,M;
    ll A[1010], B[1010];
    cin >> N >> M;
    bool flg = true;
    rep(i,0,N){
        cin >> A[i];
        mp_a[A[i]]++;
        if(mp_a[A[i]] == 2) flg = false;
    }
    rep(i,0,M){
        cin >> B[i];
        mp_b[B[i]]++;
        if(mp_b[B[i]] == 2) flg = false;
    }
    sort(A,A+N);
    sort(B,B+M);
    // printa(A,N);
    // printa(B,M);
    ll ans = 1;
    ll cnt = 0;
    rrep(i,N*M,1){
        ll v1 = lower_bound(A, A+N, i) - A;
        ll v2 = lower_bound(B, B+M, i) - B;
        // print2("i=",i);
        // print2(v1,v2);
        if(v1 == N || v2 == M){
            flg = false;
            break;
        }
        ll alt = (N - v1) * (M - v2);
        // print(alt);
        alt -= cnt;
        if(alt < 0){
            flg = false;
            break;   
        }
        if(mp_a[i] == 1 && mp_b[i] == 1){
            ans *= 1;
            cnt++;
        }else if(mp_a[i] == 1){
            ans *= (M-v2);
            ans %= MOD;
            cnt++;

        }else if(mp_b[i] == 1){
            ans *= (N-v1);
            ans %= MOD;
            cnt++;

        }else{ 
            ans *= alt;
            ans %= MOD;
            cnt++;
        }
    }
    if(!flg){
        print(0);
    }else{
        print(ans % MOD);
    }
}


Measured memory_bytes: 2304
#include<bits/stdc++.h>
using namespace std;
#define rep(j,n) for(int i=(int)(j);i<(int)(n);i++)
int main(){
  int N;
  cin>>N;
  string S;
  cin>>S;
  bitset<10> A;
  int ans=0;
  rep(0,N-2){
    int X=S.at(i)-'0';
    if(!A.test(X)){
      A.set(X,1);
      bitset<10> B;
      for(int j=i+1;j<N-1;j++){
        int Y=S.at(j)-'0';
        if(!B.test(Y)){
          B.set(Y,1);
          bitset<10> C;
          for(int k=j+1;k<N;k++){
            int Z=S.at(k)-'0';
            if(!C.test(Z)){
              C.set(Z);
              ans++;
            }
          }
        }
      }
    }
  }
  cout<<ans<<endl;
}

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

using namespace std;

int main()
{
	int n, m, x;
	cin >> n >> m >> x;
	vector<int> v(m+1);
	for (int i = 0; i < m; i++) cin >> v[i];
	v[m] = x;
	sort(v.begin(), v.end());
	int k = lower_bound(v.begin(), v.end(), x) - v.begin();
	cout << min(k, m-k) << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pi 3.141592653589793238
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb push_back
#define bg begin()
#define end end()
#define sz size()
#define vi vector<int>
#define vl vector<long long int>
int main(){
	fast;
	ll n;
	cin>>n;
	if(n%1000)
		cout<<1000 - n%1000;
	else
		cout<<"0";
	return 0;
}



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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
    return string(1, val);
}

// 最大公約数
int gcd(int a, int b) {
   if (a%b == 0) {
       return(b);
   } else {
       return(gcd(b, a%b));
   }
}

// 最小公倍数
int lcm(int a, int b) {
   return a / gcd(a, b) * b;
}

int main(){
    int N; cin >> N;
    vector<ll> a(N); REP(i, N) cin >> a[i];

    ll res = 0;
    for(int i = 0; i < N; ++i) {
        res = res + a[i] - 1;
    }

    cout << res << endl;
}

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

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

using namespace std;

int main()
{
  int n;
  cin >> n;
  vector<int> L(n);
  rep(i, n) cin >> L[i];

  sort(L.begin(), L.end());
  int ans = 0;
  rep(b,n) rep(a,b)
  {
    int ab = L[a] + L[b];
    int r = lower_bound(L.begin(), L.end(), ab) - L.begin();
    int l = b + 1;
    ans += r - l;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 384
package main

import (
  "fmt"
  "sort"
)

func biL(a []int, x int) int {return sort.SearchInts(a, x)}
func biR(a []int, x int) int {return sort.Search(len(a), func(i int) bool {return a[i] > x})}

func maxInt(a ...int) int {m := a[0]; for _, x := range a {if x > m {m = x}}; return m}
func minInt(a ...int) int {m := a[0]; for _, x := range a {if x < m {m = x}}; return m}

func main() {
  var n, m, x int 
  fmt.Scan(&n, &m, &x)
  a := make([]int, m)
  for i := 0; i < m; i++ {
    fmt.Scan(&a[i])
  }
  i := biL(a, x)
  fmt.Println(minInt(i, m - i))
}

Measured memory_bytes: 512
#include<iostream>
#include<algorithm>
#include<vector>
#include<numeric>
#include<string>
#include<cmath>
#include<set>
#include<queue>
#include<bitset>
#include<iomanip>
#include<cctype>

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,a,b) for (int (i)=a;(i)<(b);(i)++)
#define all(x) (x).begin(),(x).end()

using namespace std;
const int inf = 1001001000;

void print(vector<vector<int>> a){
	for (int i=0;i<a.size();i++){
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<int> a){
    int n = a.size();
    for (int j=0;j<n;j++) {
        if (j != n-1) cout << a[j] << " ";
        else cout << a[j] << endl;
    }
}

//mod計算用のクラス
class ModInt{
public:
    long long int x;
    long long int mod;
	ModInt(){}
    ModInt(long long int _x, long long int _mod = 1000000007){
        this->x = _x % _mod;
        this->mod = _mod;
    }
	ModInt operator+(ModInt other){
		return ModInt(this->x + (other.x % this->mod),this->mod);
	}
	ModInt operator-(ModInt other){
		long long int res = this->x - (other.x % this->mod);
		if (res < 0) return ModInt(res + this->mod, this->mod);
		return ModInt(res);
	}
	ModInt operator*(ModInt other){
		return ModInt(this->x * (other.x % this->mod),this->mod);
	}
	ModInt operator/(ModInt other){
		return ModInt(*this * other.inv());
	}
	ModInt pow(long long int n){
		ModInt res(1, this->mod), a(this->x, this->mod);
		while (n){
			if (n & 1){
				res = res * a;
			}
			n >>= 1;
			a = a * a;
		}
		return res;
	}
	ModInt inv(){
		return ModInt(this->pow(this->mod - 2));
	}
	void disp(){
		cout << this->x << endl;
	}
};
ostream& operator<<(ostream& stream, const ModInt m){
	stream << to_string(m.x);
	return stream;
}


int main(){
	int n;
	cin >> n;
	vector<int> r(n + 1, 0);
	ModInt ans(1);
	r[0] = 3;
	rep(i, n)
	{
		int now; cin >> now;
		if (r[now] == 0){
			cout << 0 << endl;
			return 0;
		}
		ans = ans * ModInt(r[now]);
		r[now]--;
		r[now + 1]++;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 640
from bisect import bisect_left,bisect_right
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort()
c.sort()
ans=0

for i in range(n):
    ai=bisect_left(a,b[i])
    ci=bisect_right(c,b[i])
    ans+=ai*(n-ci)
print(ans)


Measured memory_bytes: 23232
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const ll INF = 1e18;
#define pu push
#define pb push_back
#define mp make_pair
#define print(x) cout << (x) << endl;
#define rep(i,n) for(ll i = 0; i < (n); i++)
#define SORT(x) sort(x.begin(),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define fi first
#define sc second

int main() {
    int N, M;
    cin >> N >> M;
    if (N%4==1||N%4==3) {
        for (int i = 0; i < M; i++) {
            cout << (N+1)/2-1-i << " " << (N+1)/2+i << endl;
        }
    } else if (N%4==0&&N/4<M)
    {
        for (int i = 0; i < N/4; i++) {
            cout << (N+1)/2-1-i << " " << (N+1)/2+i << endl;
        }
        for (int i = N/4; i < M; i++) {
            cout << (N+1)/2-1-i << " " << (N+1)/2+1+i << endl;
        }
    } else if (N%4==0) {
        for (int i = 0; i < M; i++) {
            cout << (N+1)/2-1-i << " " << (N+1)/2+i << endl;
        }
    } else if (N%4==2&&N/4<M) {
        for (int i = 0; i < N/4; i++) {
            cout << (N+1)/2-1-i << " " << (N+1)/2+i << endl;
        }
        for (int i = N/4; i < M; i++) {
            cout << (N+1)/2-1-i << " " << (N+1)/2+1+i << endl;
        }
    } else if (N%4==2) {
        for (int i = 0; i < M; i++) {
            cout << (N+1)/2-1-i << " " << (N+1)/2+i << endl;
        }
    }
}

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

long long mod(long long val, long long m) {
  long long res = val % m;
  if (res < 0) res += m;
  return res;
}

int main() {
  int N, K; cin >> N >> K;
  vector<int> A(N);
  for (int i = 0; i < N; i++) cin >> A.at(i);
  const int MOD = 1000000007;
  // dp[i][j] := i 番目の子どもまでで j 個の飴を分け合う方法の総数
  vector<vector<long long>> dp(N+1, vector<long long>(K+1, 0));
  dp.at(0).at(0) = 1;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j <= K; j++) {
      // dp[i+1][*] への遷移 : 区間 [j, j + a_i] に dp[i][j] を加算 (いもす的に)
      dp.at(i+1).at(j) += dp.at(i).at(j);
      dp.at(i+1).at(j) = mod(dp.at(i+1).at(j), MOD);
      if (j + A.at(i) + 1 <= K) {
        dp.at(i+1).at(j + A.at(i) + 1) -= dp.at(i).at(j);
        dp.at(i+1).at(j + A.at(i) + 1) = mod(dp.at(i+1).at(j + A.at(i) + 1), MOD);
      }
    }
    for (int j = 0; j < K; j++) {
      dp.at(i+1).at(j+1) += dp.at(i+1).at(j);
      dp.at(i+1).at(j+1) = mod(dp.at(i+1).at(j+1), MOD);
    }
  }
  cout << dp.at(N).at(K) << endl;
}

Measured memory_bytes: 80256
IDENTIFICATION DIVISION.
PROGRAM-ID. PROGRAM_ID.

DATA DIVISION.
WORKING-STORAGE SECTION.
01 N          PIC 9(10).
01 ans        PIC 9(10).
01 zs         PIC Z(9)9.

PROCEDURE DIVISION.
  ACCEPT N.
  COMPUTE ans = N ** 3.
  MOVE ans TO zs.
  DISPLAY FUNCTION TRIM(zs).
  STOP RUN.


Measured memory_bytes: 3864
n = int(input())
s = dict()
for i in range(0,n):
    a = list(input())
    a.sort()
    if str(a) in s:
        s[str(a)] += 1
    else:
        s[str(a)] = 1
ans = 0
for i in s:
    k = s[i]
    ans += int(k*(k-1)/2)

print(ans)

Measured memory_bytes: 22092
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <utility>
using namespace std;

int main()
{
    int N, M;
    cin>>N>>M;
    vector<int> A(N), B(N), C(N);
    for (int i=0; i<N; i++)
        cin>>A[i]>>B[i]>>C[i];
    vector<int> D(M), E(M), F(M);
    for (int i=0;i <M; i++)
        cin>>D[i]>>E[i]>>F[i];

    map<int, int> MX;
    MX[0] = 0;
    for (int i=0; i<N; i++)
    {
        MX[A[i]] = 0;
        MX[B[i]] = 0;
    }
    for (int i=0; i<M; i++)
        MX[D[i]] = 0;
    int c = 0;
    vector<int> VX;
    for (auto &m: MX)
    {
        VX.push_back(m.first);
        m.second = c++;
    }

    map<int, int> MY;
    MY[0] = 0;
    for (int i=0; i<N; i++)
        MY[C[i]] = 0;
    for (int i=0; i<M; i++)
    {
        MY[E[i]] = 0;
        MY[F[i]] = 0;
    }
    c = 0;
    vector<int> VY;
    for (auto &m: MY)
    {
        VY.push_back(m.first);
        m.second = c++;
    }

    int w = (int)MX.size();
    int h = (int)MY.size();

    vector<string> T(2*h, string(2*w, '.'));
    for (int i=0; i<N; i++)
    {
        int y = MY[C[i]]*2;
        for (int x=MX[A[i]]*2; x<=MX[B[i]]*2; x++)
            T[y][x] = '#';
    }
    for (int i=0; i<M; i++)
    {
        int x = MX[D[i]]*2;
        for (int y=MY[E[i]]*2; y<=MY[F[i]]*2; y++)
            T[y][x] = '#';
    }

    vector<pair<int, int>> Q;
    T[MY[0]*2][MX[0]*2] = '*';
    Q.push_back(make_pair(MX[0]*2, MY[0]*2));
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};
    for (int q=0; q<(int)Q.size(); q++)
    {
        int x = Q[q].first;
        int y = Q[q].second;
        for (int d=0; d<4; d++)
        {
            int tx = x + dx[d];
            int ty = y + dy[d];
            if (0<=tx && tx<2*w && 0<=ty && ty<2*h &&
                T[ty][tx]=='.')
            {
                T[ty][tx] = '*';
                Q.push_back(make_pair(tx, ty));
            }
        }
    }

    //for (string t: T)
    //    cout<<t<<endl;

    long long ans = 0;
    for (int y=0; y<2*h; y++)
        for (int x=0; x<2*w; x++)
            if (T[y][x]=='*')
            {
                if (x==0 || y==0 || x==2*w-1 || y==2*h-1)
                {
                    cout<<"INF"<<endl;
                    return 0;
                }

                ans += (long long)(VX[(x+1)/2]-VX[x/2])*(VY[(y+1)/2]-VY[y/2]);
            }
    cout<<ans<<endl;
}


Measured memory_bytes: 300816
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
const int Maxn=2e5+5;
long long n,a[Maxn],f[Maxn],tmp[Maxn],ans;
int k;
void msort(int l,int r)
{
	if(l==r)return;
	int mid=(l+r)>>1;
  	msort(l,mid);msort(mid+1,r);
  	int i=l,j=mid+1,k=l;
  	while(i<=mid&&j<=r)
	{
    	if(f[i]<=f[j])
      		tmp[k++]=f[i++];
    	else
		{
      		tmp[k++]=f[j++];
      		ans+=(mid-i+1);
    	}
  	}
  	while(i<=mid)tmp[k++]=f[i++];
  	while(j<=r)tmp[k++]=f[j++];
  	for(i=l;i<=r;i++)
    	f[i]=tmp[i];
}
int main()
{
	//freopen("std.in","r",stdin);
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		f[i]=f[i-1]+a[i]-k;
	}
	msort(0,n);
	cout<<n*(n+1ll)/2ll-ans;
	return 0;
}

Measured memory_bytes: 4992
N = int(input())
hs = list(map(int, input().split()))

count = 0
for h in range(1, 101):
    found = False
    for i in range(N):
        if hs[i] >= h:
            if not found:
                count += 1
                found = True
        elif found:
            found = False
print(count)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int a[10005],ans,n;
int main(void){
    cin>>n;
    for(int i=1;i<=2*n;i++) cin >> a[i];
    sort(a+1,a+1+2*n);
    for(int i=1;i<=2*n;i+=2) ans+=a[i];
    cout<<ans<<"\r\n";
}

Measured memory_bytes: 256