akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

// c++11
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>

#define mp make_pair
#define mt make_tuple
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

const int INF = 1 << 29;
const ll LL_INF = 1LL << 60;
const double EPS = 1e-9;
const ll MOD = 1000000007;

const int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
int N;
vector<int> A;
int main()
{
    cin >> N;
    A.resize(N);
    for (auto &val : A)
    {
        cin >> val;
        if (val >= N)
        {
            cout << -1 << endl;
            return 0;
        }
    }
    // impossible
    if (A[0] != 0)
    {
        cout << -1 << endl;
        return 0;
    }
    int pre = A[N - 1];
    for (int i = N - 2; i >= 0; i--)
    {
        pre--;
        if (A[i] < pre){
            cout << -1 << endl;
            return 0;
        }
        pre = max(pre, A[i]);
    }

    pre = A[0];
    ll result = 0;
    for (int i = 1; i < N; i++)
    {
        const int val = A[i];
        if (pre + 1 == val)
        {
            pre = val;
            continue;
        }
        if (pre == val)
        {

            result += pre;
            pre = val;
            continue;
        }
        if (pre > val)
        {
            result += pre;
            pre = val;
            continue;
        }
        if (pre < val)
        {
            result += pre;
            pre = val;
            continue;
        }
    }
    result += pre;
    cout << result << endl;
    return 0;
}


Measured memory_bytes: 1024
l = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
n = int(input())
print(l[n-1])

Measured memory_bytes: 2940
N,k = map(int,input().split())

s = list(map(int,input().split()))
s.sort()

count = 0
for i in range(N):
	if k - s[i] >= 0:
		count += 1
		k -= s[i]
	else:
		break

if count == N :
	if k>0:
		count -= 1
	print(count)
else:
	print(count)

Measured memory_bytes: 3064
N = int(input())
a = [[0]*N for i in range(3)]
for i in range(N):
    bin = [int(i) for i in input().split()]
    for j in range(3):
        a[j][i] = bin[j]

dp = [[0]*(N+1) for i in range(3)]
for i in range(3):
    dp[i][1] = a[i][0]
ls = [0, 1, 2]

for i in range(2, N+1):
    for j in ls:
        for k in ls:
            if j != k:
                dp[j][i] = max(dp[j][i], dp[k][i-1] + a[j][i-1])
ans = 0
for i in range(3):
    ans = max(ans, dp[i][N])
print(ans)

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

int main() {
  int A, B;
  int c = 0;
  cin >> A >> B;
  for (int i = A; i <= B; i++) {
    if (i / 10000 == i % 10) {
      if ((i % 10000) / 1000 == (i % 100) / 10) {
        c += 1;
      }
    }
  }
  cout << c << endl;
}


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

int k;
vector<int> v, num;

void enu0(int i, int x){
    if(i == 5){
        v.push_back(x);
    }
    else{
        for(int j = 0; j < 10 - k; j++){
            enu0(i + 1, 10 * x + num[j]);
        }
    }
}

void enu1(int m, int i, int x){
    if(i == m){
        v.push_back(x);
    }
    else{
        for(int j = 0; j < 10 - k; j++){
            enu1(m, i + 1, 10 * x + num[j]);
        }
    }
}

int main()
{
    int n;
    cin >> n >> k;
    v = {};
    num = {};
    int d[10];
    bool g = true;
    for(int i = 0; i < k; i++){
        cin >> d[i];
        if(d[i] == 0){
            g = false;
        }
    }
    for(int i = 0; i < 10; i++){
        bool f = true;
        for(int j = 0; j < k; j++){
            if(i == d[j]){
                f = false;
            }
        }
        if(f){
            num.push_back(i);
        }
    }
    if(g){
        enu0(0, 0);
    }
    else{
        for(int i = 1; i <= 5; i++){
            enu1(i, 0, 0);
        }
    }
    int s = v.size();
    for(int i = 0; i < s; i++){
        if(v[i] >= n){
            cout << v[i] << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 892
#define _USE_MATH_DEFINES
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <clocale>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i, s, n) for(int i = (s), i##_len=(n); i < i##_len; ++i)
#define FORS(i, s, n) for(int i = (s), i##_len=(n); i <= i##_len; ++i)
#define VFOR(i, s, n) for(int i = (s); i < (n); ++i)
#define VFORS(i, s, n) for(int i = (s); i <= (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) FORS(i, 0, n)
#define VREP(i, n) VFOR(i, 0, n)
#define VREPS(i, n) VFORS(i, 0, n)
#define RFOR(i, s, n) for(int i = (s), i##_len=(n); i >= i##_len; --i)
#define RFORS(i, s, n) for(int i = (s), i##_len=(n); i > i##_len; --i)
#define RREP(i, n) RFOR(i, n, 0)
#define RREPS(i, n) RFORS(i, n, 0)
#define IREP(i, v) for(auto i = (v).begin(); i != (v).end(); ++i)
#define IRREP(i, v) for(auto i = (v).rbegin(); i != (v).rend(); ++i)
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v), greater<decltype(v[0])>())
#define SZ(x) ((int)(x).size())
#define REV(x) reverse(ALL(x))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end())

using ld = long double;
using ll = long long;
using ui = unsigned int;
using ull = unsigned long long;
using Pi_i = pair<int, int>;
using Pll_ll = pair<ll, ll>;
using VB = vector<bool>;
using VC = vector<char>;
using VD = vector<double>;
using VI = vector<int>;
using VLL = vector<ll>;
using VS = vector<string>;
using VSH = vector<short>;
using VULL = vector<ull>;

const int MOD = 1000000007; 
const int INF = 1000000000; //1e9
const int NIL = -1;
const ll LINF = 1000000000000000000; // 1e18
const double EPS = 1E-10;

template<class T, class S>
bool chmax(T &a, const S &b){
    if(a < b){
        a = b; return true;
    }
    return false;
}
template<class T, class S>
bool chmin(T &a, const S &b){
    if(b < a){
        a = b; return true;
    }
    return false;
}


int gcd(int a, int b){
    if(!b) return a;
    if(a % b) return gcd(b, a % b);
    return b;
}

int main(){
    int N, K; cin >> N >> K;
    VI A(N);
    int mx(0), g;
    REP(i, N){
        cin >> A[i];
        chmax(mx, A[i]);
        if(i) g = gcd(g, A[i]);
        else g = A[0];
    }
    cout << ((mx >= K && !(K % g)) ? "" : "IM") << "POSSIBLE" << endl;
    return 0;
}


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

using namespace std;


int main(){

    int n, k;
    string s;
    cin >> n >> k;
    cin >> s;

    vector<int> Nums;
    int cnt = 0;
    int now = 1;
    for (int i = 0; i < n; i++) {
        if (s[i] == (char)('0' + now)) cnt++;
        else {
            Nums.push_back(cnt);
            now  = 1 - now;
            cnt = 1;
        }
    }
    if (cnt != 0) Nums.push_back(cnt);
    if (Nums.size() % 2 == 0) Nums.push_back(0);

    int Add = 2 * k + 1;

    vector <int> sum(Nums.size() + 1);
    for (int i = 0; i < Nums.size(); i++) {
        sum[i+1] = sum[i] + Nums[i];
    }

    int ans = 0;
    int temp = 0;
    for (int i = 0; i < Nums.size(); i += 2) {
        
        int left = i;
        int right = min(i + Add, (int)Nums.size());
        int temp = sum[right] - sum[left];
        ans = max(ans, temp);
    }

    cout << ans << '\n';

}
 

Measured memory_bytes: 1272
from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
from fractions import gcd
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
EPS = 10**-7

a, b = map(int, input().split())

big = 100000
ans = big + 1
for i in range(big, 0, -1):
    if int(i*0.08) == a and int(i*0.1) == b:
        ans = i
    
if ans <= big:
    print(ans) 
else:
    print(-1)

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

#define newline printf("\n")
#define nl '\n'
#define ll long long 
#define ui unsigned int
#define ul unsigned long

using namespace std;

int main()
{
	int K;
	string S;

	cin >> K >> S;

	string result = (S.length() > K) ? S.substr(0, K) + "..." : S;

	cout << result << nl;

	return 0;
}


Measured memory_bytes: 3596
N = int(input())
A = [int(i) for i in input().split()]
A.sort()
B=[0 for i in range(N+1)]
for i in range(N):
    B[i+1]=B[i]+A[i]
B=B[1:]
cnt=1
for i in range(N-1):
    if 2*B[i]<A[i+1]:
        cnt=0
    cnt+=1
print(cnt)


Measured memory_bytes: 14304
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.IntStream;

/**
 * 解説どおりに作成したソースコード
 */
public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int n = scanner.nextInt(), m = scanner.nextInt();
			int[] a = new int[m], b = new int[m];
			boolean[][] graph = new boolean[n][n];
			IntStream.range(0, n).forEach(i -> Arrays.fill(graph[i], false));
			IntStream.range(0, m).forEach(i -> {
				a[i] = scanner.nextInt() - 1;
				b[i] = scanner.nextInt() - 1;
				graph[a[i]][b[i]] = graph[b[i]][a[i]] = true;
			});
			boolean[] visited = new boolean[n];
			System.out.println(IntStream.range(0, m).filter(i -> {
				Arrays.fill(visited, false);
				graph[a[i]][b[i]] = graph[b[i]][a[i]] = false;
				dnf(graph, visited, 0);
				graph[a[i]][b[i]] = graph[b[i]][a[i]] = true;
				return IntStream.range(0, n).filter(j -> !visited[j]).count() > 0;
			}).count());
		}
	}

	/**
	 * グラフの遍歴処理
	 * 
	 * @param graph   グラフを表す配列
	 * @param visited 各ノードが処理されたかどうかを表す配列
	 * @param node    現在処理しているノード
	 */
	private static void dnf(final boolean[][] graph, boolean[] visited, int node) {
		visited[node] = true;
		IntStream.range(0, visited.length).filter(i -> graph[node][i]).forEach(i -> {
			if (!visited[i]) {
				dnf(graph, visited, i);
			}
		});
	}
}


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

#define ll long long
#define pll pair<ll,ll>
#define all(v) v.begin(),v.end()
#define xx first
#define yy second
#define mx 1000000000000000000

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

    ll n;
    cin >> n;

    ll fk = n;

    vector<ll> ds;

    for(ll i=2;i*i<=n;i++)
    {
        ll x = i;
        while(n%i == 0) ds.push_back(x), x*=i, n/=i;
    }

    if(n!=1) ds.push_back(n);

    sort(all(ds));

    ll ans = 0;
    for(ll p : ds)
        if(fk%p == 0) fk/=p, ans++;

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3660
import std.stdio, std.conv, std.functional, std.string;
import std.algorithm, std.array, std.container, std.range, std.typecons;
import std.numeric, std.math, std.random;
import core.bitop;

string FMT_F = "%.10f";

static string[] s_rd;
T RD(T = long)() { while(!s_rd.length) s_rd = readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
string RDR()() { return readln.chomp; }
T[] ARR(T = long)(in string str, T fix = 0) { auto r = str.split.to!(T[]); r[] += fix; return r; }
T[] RDA(T = long)(T fix = 0) { auto r = readln.chomp.split.to!(T[]); r[] += fix; return r; }
T[][] RDA2(T = long)(size_t n, T[] fix = []) { auto r = new T[][](n); foreach (i; 0..n) { r[i] = readln.chomp.split.to!(T[]); foreach (j, e; fix) r[i][j] += e; } return r; }
size_t[] MAKE_IDX(alias less = "a < b", Range)(Range range) { auto idx = new size_t[](range.length); makeIndex!(less)(range, idx); return idx;}
size_t MIN_POS(alias less = "a < b", Range)(Range range) { auto r = minPos!(less)(range); return range.length - r.length; }

bool inside(T)(T x, T b, T e) { return x >= b && x < e; }
long lcm(long x, long y) { return x * y / gcd(x, y); }

long mod = 10^^9 + 7;
//long mod = 998244353;
//long mod = 1_000_003;
void moda(ref long x, long y) { x = (x + y) % mod; }
void mods(ref long x, long y) { x = ((x + mod) - (y % mod)) % mod; }
void modm(ref long x, long y) { x = (x * y) % mod; }

void main()
{
	auto N = RD;
	auto A = new long[][](N);
	foreach (i; 0..N)
	{
		A[i] = RDA(-1L);
	}

	long[] open;
	foreach (i; 0..N) open ~= i;
	//open ~= -1;
	auto used = new long[](N);
	while (!open.empty)
	{
		auto lhs = open.front; open.popFront;
		debug writeln(lhs);
		/*if (lhs == -1)
		{
			++ans;
			if (open.empty) break;
			continue;
		}*/
		
		if (A[lhs].empty) continue;
		auto rhs = A[lhs].front;
		if (A[rhs].empty)
			break;

		if (A[rhs].front == lhs)
		{
			auto d = max(used[lhs], used[rhs]) + 1;
			used[lhs] = d;
			used[rhs] = d;
			A[lhs].popFront;
			A[rhs].popFront;
			if (!A[lhs].empty)
				open ~= lhs;
			if (!A[rhs].empty)
				open ~= rhs;
		}
	}

	bool ok = true;
	foreach (i; 0..N)
	{
		if (!A[i].empty)
			ok = false;
	}

	if (ok)
	{
		long ans;
		foreach (i; 0..N)
			ans = max(ans, used[i]);
		writeln(ans);
	}
	else
		writeln(-1);
	stdout.flush();
	debug readln();
}

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

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

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

    for (int i = 0; i < N; i++)
        a[i]--;

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

    if (v == -1)
        cout << -1 << endl;
    else
        cout << N - (v + 1) << endl;

    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a) ;i < (b) ;i++)
#define repr(i, a, b) for (int i = (b) - 1 ;i >= a ;i--) 
int main(){
	int w, h, p[100000], q[100000] ;
	cin >> w >> h ;
	rep(i, 0, w)cin>>p[i] ;
	rep(j, 0, h)cin>>q[j] ;

	long ans = 0, added = 0 ;
  	sort(q,q+h,less<int>());
  	sort(p,p+w,less<int>());

  	int i = 0 ,j = 0 ;
  	
  	while(!(i >= w) || !(j >= h)){
  		if ((i < w && p[i] <= q[j]) || j >= h){
  			ans += (h + 1 - j) * long (p[i]) ;
  			i++ ;
  		}else{
  			ans += (w + 1 - i) * long (q[j]) ;
  			j++ ;
  		}

  	}

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


Measured memory_bytes: 1152
#include <stdio.h>
#include <string.h>
int main(){
    int n;
    char s[10000];
    scanf("%d\n %s",&n ,s);
    int len=strlen(s);
    for (int i=0;len>i;i++){
        int x = s[i]-'A';
        x = (x+n)%26;
        putchar('A'+x);

    }
    putchar('\n');
}

Measured memory_bytes: 128
#include<stdio.h>

int main(void) {
  char S[2000000];
  char T[2000000];
  int i, j;
  int num = 0;
  
  scanf("%s", &S);
  scanf("%s", &T);
  for(i=0; S[i]!='\0'; ++i);
  for(j = 0; j <= i; j++){
    if(S[j] != T[j]){
      num++;
    }
  }  
  printf("%d", num);
  return 0;
}


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

int r[]={};

int func(char a[3][3], char c){
	int f = 0;
	for(int i = 0;i < 3;i++){
		if(a[i][0]==c && a[i][1]==c && a[i][2]==c)return 1;
		if(a[0][i]==c && a[1][i]==c && a[2][i]==c)return 1;
	}
	if(a[0][0]==c && a[1][1]==c && a[2][2]==c)return 1;
	if(a[2][0]==c && a[1][1]==c && a[0][2]==c)return 1;
	
	return 0;
}

int main(){
	char a[3][3];
	while(cin >> a[0][0] >> a[0][1] >> a[0][2]){
		for(int i = 1;i < 3;i++)
		for(int j = 0;j < 3;j++)cin >> a[i][j];
		if(func(a, 'o'))cout << 'o' << endl;
		else if(func(a, 'x'))cout << 'x' << endl;
		else cout << 'd' << endl;
	}
	return 0;
}

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

//  四方向へのベクトル
const int dx[4] = {-1,0,1,0};
const int dy[4] = {0,-1,0,1};

int h,w,n;
//探索用
//bool seen[1000][1000];
int gh,gw,MAX=0;
long long sum=0;
int seen[2000][2000];

int bfs(const vector<string> &G,int Ncnt,int x,int y,queue <int> q){
   //x,yの順に格納
   q.push(x);
   q.push(y);
//    seen[y][x] = 0;

   while(true){
        int cc = q.front();
        q.pop();
        int rr = q.front();
        q.pop(); 
        
        //cout << "Q OF SIZE is "<<q.size() <<" next(" <<cc<<" "<<rr<<")"<<endl;
        for(int i=0;i<4;i++){
            int next_x = cc + dx[i];
            int next_y = rr + dy[i];
            //cout << next_x << " " <<next_y<<" "<<seen[next_y][next_x]<< endl;

            if(next_x<0 || next_x >=w || next_y<0 || next_y>=h) continue;
            if(seen[next_y][next_x] != -1) continue;
            if(G[next_y][next_x]  == '#') continue;

            //cout << "path" <<endl;
            

            q.push(next_x);
            q.push(next_y);
            
             seen[next_y][next_x] = seen[rr][cc] +1;
             //cout << next_x << " " << next_y << " "<<seen[next_y][next_x]<<endl;
             //cout <<"SIZE "<<q.size()<<" "<<G[next_y][next_x]<<endl;

             if(seen[next_y][next_x] > MAX) MAX = seen[next_y][next_x];
            //  if(G[next_y][next_x] - '0' == Ncnt){
            //      sum += seen[next_y][next_x];
            //      //cout <<seen[next_y][next_x]<<endl;
            //      //cout <<next_y<<" "<<next_x<<endl;
            //      memset(seen,-1,sizeof(seen));
            //      seen[next_y][next_x] = 0;
            //      while(q.size()!=2) q.pop();
                 
            //      //cout <<"a"<<Ncnt<<endl;
            //      Ncnt++;
            //      break;
            //  }
            // // cout<<seen[next_y][next_x] <<endl;

            //    dfs(G,cnt,next_x,next_y);
        }

        if(q.size() == 0) break;
   }

  return 0;
}

int main(){
    cin >> h>> w;
    int sh,sw;

    vector<string> G(h);
    for(int i=0;i<h;i++) cin >> G[i];

    queue <int> q;
    memset(seen,-1,sizeof(seen));
    for(int i=0;i<h;i++){
        for(int k=0;k<w;k++){
            if(G[i][k] == '#'){
                sh = i;
                sw = k;
                //　ループを抜ける
                q.push(sw);
                q.push(sh);
                seen[sh][sw] = 0;
            }
        }
    }

    
    //cout << seen[0][0] << endl;

    bfs(G,1,sw,sh,q);

    cout << MAX <<endl;
    return 0;
    
}



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

int main() {
    unsigned long long n, a, b, ans;
    cin >> n >> a >> b;

    if (n%(a+b)) {
        if (n > (n/(a+b))*(a+b) + a) ans = a*(n/(a+b)) + a;
        else ans = a*(n/(a+b)) + n-(n/(a+b))*(a+b);
    } else {
        ans = a*(n/(a+b));
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include<stdbool.h>
typedef long long ll;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define REP(i,l,r) for(int i=l; i<(int)(r); i++)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define swap(a,b) {ll tp=a;a=b;b=tp;}
const ll MOD = 1000000007;

int p[10];
int my_next_perm(int n){
    int i, j, tmp;
    if(n <= 1) return 0;
    for(i = n-1; i > 0 && p[i-1] >= p[i]; i--);
    if(i == 0) return 0;
    for(j = n-1; j > i && p[i-1] >= p[j]; j--);
    swap(p[i-1], p[j]);
    for(j = n-1; i < j; i++, j--)
        swap(p[i], p[j]);
    return 1;
}

int x[10], y[10];
int main(){
    int N; scanf("%d", &N);
    rep(i,N){
        scanf("%d%d", x+i, y+i);
    }

    double ans = 0.0; int num = 0;
    rep(i,N) p[i] = i;
    do{
        rep(i,N-1){
            ans += sqrt(pow(x[p[i]] - x[p[i+1]],2)+pow(y[p[i]] - y[p[i+1]],2));
        }
        num++;
    }while(my_next_perm(N));
    
    printf("%.10lf\n", (ans/num));
    return 0;
}

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

int main() {
    int a, b, m;
    cin >> a >> b >> m;
    vector<int> p(a);
    vector<int> q(b);
    int minp = 1001001001;
    int minq = 1001001001;
    for (int i = 0; i < a; ++i) {
        cin >> p[i];
        minp = min(minp, p[i]);
    }
    for (int j = 0; j < b; ++j) {
        cin >> q[j];
        minq = min(minq, q[j]);
    }
    map<pair<int, int>, int> discount;
    for (int k = 0; k < m; ++k) {
        int d, e, c;
        cin >> d >> e >> c;
        --d; --e;
        if (discount.count(make_pair(d, e))) {
            discount[make_pair(d, e)] = max(discount[make_pair(d, e)], c);
        } else {
            discount.insert(make_pair(make_pair(d, e), c));
        }
    }
    int ans = minp + minq;
    for (pair<pair<int, int>, int> k : discount) {
        int x = k.first.first;
        int y = k.first.second;
        int z = k.second;
        ans = min(ans, p[x] + q[y] - z);
    }
    cout << ans << endl;
}


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

int main() {
    int j,n,a,b;
    int d[11][7]={{0,1,1,1,1,1,1},{0,0,0,0,1,1,0},{1,0,1,1,0,1,1},{1,0,0,1,1,1,1},{1,1,0,0,1,1,0},{1,1,0,1,1,0,1},
    {1,1,1,1,1,0,1},{0,1,0,0,1,1,1},{1,1,1,1,1,1,1},{1,1,0,1,1,1,1},{0,0,0,0,0,0,0}};
    while(cin >> n && n!=-1) {
		for (a=10;n>0;n--) { cin >> b;
		for (j=0;j<7;j++) cout << (d[a][j]+d[b][j]) % 2;
		a=b; 
		cout << endl;}
	}
	return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
 
using lli = long long int;
using ll = long long ;
using ld=long double;
using d= double;
 
 
  

int main()  
{  
    string s;
    cin>>s;
    int c0=0,c1=0;
    int n=s.length();
    for(int i=0;i<n;i++){
        if(s[i]=='0')
        c0++;
        else
        c1++;
    }
    cout<<min(c0,c1)*2;
   
  
    return 0;  
}  

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
string S[2020];
short L[1504][1504],R[1504][1504];
int dp[1504][1504];


void solve() {
	int i,j,k,l,r,x,y,x2,y2; string s;
	
	cin>>N;
	FOR(y,N) {
		cin>>S[y];
		FORR(c,S[y]) {
			if(c!='#') c-='0';
			else c=0;
		}
	}
	ll ret=0;
	for(y=N-1;y>=0;y--) {
		L[y][N]=N;
		R[y][N]=-1;
		for(x=N-1;x>=0;x--) {
			int down=(y<N-1) && (S[y+1][x]>0);
			int right=(x<N-1) && (S[y][x+1]>0);
			
			if(S[y][x]==0) {
				for(y2=y;y2<N;y2++) {
					L[y][x]=N;
					R[y][x]=-1;
				}
			}
			else {
				dp[y][x]=dp[y+1][x]+dp[y][x+1];
				L[y][x]=x;
				if(down&&right) {
					R[y][x]=R[y][x+1];
					
					int r=0;
					for(y2=y+1;y2<N;y2++) {
						if(L[y2][x+1]<=R[y2][x] && r<L[y2][x+1]) {
							dp[y][x]-=dp[y2][L[y2][x+1]];
						}
						r=R[y2][x];
						R[y2][x]=max(R[y2][x],R[y2][x+1]);
						L[y2][x]=min(L[y2][x],L[y2][x+1]);
					}
				}
				else if(down) {
					R[y][x]=x;
				}
				else if(right) {
					R[y][x]=R[y][x+1];
					for(y2=y+1;y2<N;y2++) {
						L[y2][x]=L[y2][x+1];
						R[y2][x]=R[y2][x+1];
					}
				}
				else {
					R[y][x]=x;
					for(y2=y+1;y2<N;y2++) {
						L[y2][x]=N;
						R[y2][x]=0;
					}
				}
				ret+=S[y][x]*dp[y][x];
				dp[y][x]+=S[y][x];
			}
		}
	}
	
	
	cout<<ret<<endl;
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


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

const int N = 2e5 + 10;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
    }
    int ans = 0;
    for (int bit = 0; bit < 29; ++bit) {
        const int mod = 1 << (bit + 1), k = 1 << bit;
        vector<int> ta(n), tb(n);
        for (int i = 0; i < n; ++i) {
            ta[i] = a[i] & (mod - 1);
            tb[i] = b[i] & (mod - 1);
        }
        sort(tb.begin(), tb.end());
        int tot = 0;
        for (int i = 0; i < n; ++i) {
            [&]() {
                auto itl = lower_bound(tb.begin(), tb.end(), k - ta[i]);
                auto itr = upper_bound(tb.begin(), tb.end(), mod - ta[i] - 1);
                if (itl == tb.end() || itr == tb.begin()) return;
                if (itl >= itr) return;
                tot = (tot + (itr - itl)) % 2;
            }();
            [&]() {
                auto it = lower_bound(tb.begin(), tb.end(), mod - ta[i] + k);
                if (it == tb.end()) return;
                tot = (tot + (tb.end() - it)) % 2;
            }();
        }
        if (tot & 1) ans |= 1 << bit;
    }
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 6376
// Sasageyo! Sasageyo! Shinzou wo Sasageyo !
// https://goo.gl/IwJzbx

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> II;
typedef vector<II> VII;
typedef vector<int> VI;
typedef vector< VI > VVI;

typedef long long int LL;

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(a) (int)(a.size())
#define ALL(a) a.begin(),a.end()
#define SET(a,b) memset(a,b,sizeof(a))
#define si(n) scanf("%d",&n)
#define dout(n) printf("%d\n",n)
#define sll(n) scanf("%lld",&n)
#define lldout(n) printf("%lld\n",n)

#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)

#define endl '\n'
const int N = 1e5 + 1;
VI g[N];
int vis[N];
int depth[N];
int par[N];
void dfs(int u, int d, int p) {
  vis[u] = 1;
  depth[u] = d;
  par[u] = p;
  for(auto c:g[u])if(!vis[c])
    dfs(c, d + 1, u), vis[u] += vis[c];
}
int main()
{
	fast_io;
  int n;
  cin >> n;
  for(int i=0;i<n-1;i++) {
    int a, b;
    cin >> a >> b;
    g[a].PB(b);
    g[b].PB(a);
  }
  dfs(1, 0, -1);
  int cnode = n;
  for(int i=1;2*i<depth[n];i++) {
    cnode = par[cnode];
  }
  string ans = "Fennec";
  if(2*vis[cnode] >= n)
    ans = "Snuke";
  cout << ans << endl;
	return 0;
}

Measured memory_bytes: 13184
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define dbg(x) cerr << #x << " = " << x << endl
#define _ << ' ' <<
using namespace std;
using ll = long long;
using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;

ll f(ll n)
{
    switch (n & 3)
    {
        case 0: return n;
        case 1: return 1;
        case 2: return n + 1;
        case 3: return 0;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll a, b;
    cin >> a >> b;
    ll sol = f(b);
    if (a != 0)
        sol ^= f(a - 1);
    cout << sol;
}


Measured memory_bytes: 256
N = int (input ())
A = [int (x) for x in input().split()]
S = sum (A)
X = 0
for i in range (N-1):
  X += A[i]*(S-A[i])
  S -= A[i]
  if X > 10**9+7:
    X = X%(10**9+7)
print (X)

Measured memory_bytes: 31544
from pprint import pprint
import sys

v_max = (10 ** 3) * 100
inf = 10 ** 10
# print(v_max)
N, W = map(int, sys.stdin.readline().strip().split(" "))

w = []
for _ in range(N):
    w_i, v_i = map(int, sys.stdin.readline().strip().split(" "))
    w.append((w_i, v_i))

dp = []
for _ in range(N+1):
    dp.append([inf] * (v_max+1))
dp[0][0] = 0

ans = 0
for i in range(N):
    for j in range(v_max+1):
        if j - w[i][1] >= 0 and W >= dp[i][j - w[i][1]] + w[i][0]:
            # dp[i+1][j] = max(dp[i][j - w[i][0]] + w[i][1], dp[i+1][j])
            dp[i+1][j] = dp[i][j - w[i][1]] + w[i][0]
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])
        if dp[i+1][j] <= W:
            # print(dp[i+1][j], j)
            # ans = max(ans, dp[i+1][j])
            ans = max(ans, j)
# pprint(dp)
print(ans)

Measured memory_bytes: 121836
s=str(input())
if(s[0]!='A'):
    print('WA')
elif(s[2:len(s)-1].count('C')!=1):
    print('WA')
else:
    flag=0
    for i in s:
        if(ord(i)<97):
            if(i!='A' and i!='C'):
                flag=1
    if(flag==1):
        print('WA')
    else:
        print('AC')

Measured memory_bytes: 3064
r, a = 0, 0

while s = gets
  break if s.nil? || s.chomp == ''

  s1, s2, d = s.split(',').map(&:to_i)
  
  if s1**2 + s2**2 == d**2
    r += 1
  elsif s1 == s2
    a += 1
  end 
end

puts r
puts a

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

int main()
{
	int N, K;
	cin >> N >> K;
	int ans = 0;
	for (int i = 0; i < N; ++i)
	{
		int h;
		cin >> h;
		if (h >= K)
			ans++;
	}
	cout << ans << '\n';
}


Measured memory_bytes: 256
using System;
class B{
  public static void Main(){
    var a = Console.ReadLine();
    var ans = 1000;
    for (int i = a.Length - 3; i >= 0; i--)
    {
      var dif = Math.Abs(int.Parse(string.Format("{0}{1}{2}", a[i], a[i+1],a[i+2])) - 753);
      if (dif < ans) ans = dif;
    }
    Console.WriteLine(ans);
  }
}

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

#define pb push_back
#define mp make_pair
#define F(i, a, n, b) for(int i=a;i<n;i+=b)
#define REVF(i, a, b, c) for(int i=a;i>=b;i-=c)
#define REP(i, n) F(i, 0, n, 1)
#define REP1(i, n) F(i, 1, n+1, 1)
#define REV(i, n) REVF(i, n, 0, 1)
#define PTR(it, x) for(auto it=x.begin();it!=x.end();++it)
#define MOD 1000000007

typedef unsigned long long ll;

const ll MAX = 1e10;

int a,b;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin>>a>>b;
	if((a == 1 && b == 2) || (b == 1 && a == 2))
		cout<<3;
	else if((a == 1 && b == 3) || (b == 1 && a == 3))
		cout<<2;
	else
		cout<<1;
	return 0;
}

Measured memory_bytes: 256
#my ($a,$b,$c,$d)=(2,3,6,6);
my ($a,$b,$c,$d)=get.words;
my $e=($a-$c+($b-$d)i).polar;
my $f=$e[0].unpolar($e[1]-pi/2)+$c+$d*i;
my $g=($c+$d*i-$f).polar;
my $h=$g[0].unpolar($g[1]-pi/2)+$f;
(|$f.reals,|$h.reals)>>.round>>.say


Measured memory_bytes: 67352
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        boolean[] a = new boolean[n];
        long[] g = new long[n];

        for (int k=0;k<n;k++){
            a[k] = false;
            g[k] = 0;
        }

        for (int i=0;i<m;i++){
            int t = scan.nextInt();
            a[t-1] = true;
        }

        if (n == 1){
            if (m == 1){
                System.out.println(0);
            }
            else{
                System.out.println(1);
            }
            return;
        }
        long sum = 0;
        g[0] = 1;
        g[1] = 1;
        if (a[0] == true){
            g[1] = 0;
        }
        sum = find(2, n, a, g);
        long q = 1000000007;
        System.out.println((long) sum % q);
    }

    static long find(int current, int n, boolean[] a, long[] g){
        
        if (current == n){
            return g[n-1]+g[n-2];
        }
        
        if (a[current-1] == true){
            g[current] = 0;
        }
        else{
            g[current] = g[current-1] + g[current-2];
        }
        long q = 1000000007;
        g[current] = (long) g[current] % q;
        return (long) find(current + 1, n, a, g);
    }
}

Measured memory_bytes: 68932
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Collection;
import java.util.Scanner;
import java.util.Deque;
import java.util.ArrayDeque;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		Scanner in = new Scanner(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		D solver = new D();
		solver.solve(1, in, out);
		out.close();
	}

	static class D {
		public void solve(int testNumber, Scanner in, PrintWriter out) {
			Deque<String> s = new ArrayDeque<>();
			s.addLast(in.next());
			int n = in.nextInt();

			boolean reverse = false;
			for (int i = 0; i < n; i++) {
				int t = in.nextInt();

				if (t == 1) {
					reverse = !reverse;
				} else {
					int f = in.nextInt();
					String ss = in.next();
					if (f == 1 ^ reverse) {
						s.addFirst(ss);
					} else {
						s.addLast(ss);
					}
				}
			}

			StringBuilder sb = new StringBuilder();
			while (!s.isEmpty()) {
				sb.append(s.pop());
			}

			if (reverse) {
				out.println(sb.reverse());
			} else {
				out.println(sb);
			}
		}

	}
}



Measured memory_bytes: 155976
#include <stdio.h>

int main(void){
  int num;
  int strt;
  int g;
  int ans;
  int tmp;
  int i;

  scanf("%d %d", &num, &strt);

  scanf("%d", &ans);
  ans -= strt;
  if(ans < 0){
    ans *= -1;
  }
  for(i = 1; i < num; i++){
    scanf("%d", &g);
    g -= strt;
    if(g < 0){
      g *= -1;
    }
    if(ans < g){
      tmp = g;
      g = ans;
      ans = tmp;
    }
    while(ans % g != 0){
      tmp = ans;
      ans = g;
      g = tmp % g;
    }
    ans = g;
  }

  printf("%d\n", ans);

  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
#define trace(x) cerr<<#x<<": "<<x<<" "<<endl
#define trace2(x, y) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z) cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define sa(a, n) for(int i =0 ; i<n ; i++) cin>>a[i]
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a  ,min(b, c))
#define scan() int n; cin>>n ; int a[n]; for(int i = 0 ; i<n ; i++) cin>>a[i]
#define print(a, n) for(int i = 0 ; i < n ; i++) cout<<a[i]<<' '
using namespace std;

int32_t main()
{
    int n;
    cin>>n;
    vector<int> arr(n+1);
    for(int i=1;i<n+1;i++)
    {
        cin>>arr[i];
    }
    int dp[n+1];
    dp[0] = 0;
    dp[1] = 0;
    dp[2] = abs(arr[2] - arr[1]);
    for(int i=3;i<n+1;i++)
    {
        dp[i] = min(dp[i-1] + abs(arr[i] - arr[i-1]), dp[i-2] + abs(arr[i] - arr[i-2]));
    }
    cout<<dp[n];
    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
using namespace std;
int a[61210];
int main(){
	for(int i=1;i<=101;i++){
		for(int j=1;j<=101;j++){
			for(int k=1;k<=101;k++){
				a[i*i+j*j+k*k+i*j+j*k+k*i]++;
			}
		}
	}
	int n;
	cin >> n;
	for(int i=1;i<=n;i++){
		cout << a[i] << endl;
	} 
	return 0;
}

Measured memory_bytes: 3820
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_set>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<complex>
#include<tuple>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;




int main(){
    string s;
    cin>>s;
    vector<ll> Mnext(26,0);
    vector<vector<ll>> back(s.size()+1,Mnext);
    for(int i=0;i<s.size();i++){
        back[i+1]=Mnext;
        Mnext[s[i]-'a']=i+1;
    }
    for(int i=0;i<26;i++){Mnext[i]=s.size();}
    vector<vector<ll>> next(s.size()+1,Mnext);
    for(ll i=s.size()-1;i>=0;i--){
        next[i]=Mnext;
        Mnext[s[i]-'a']=i;
    }
    ll k;
    cin>>k;
    ll ans=0;
    vector<vector<vector<ll>>> dp(s.size()+1,vector<vector<ll>>(s.size()+1,vector<ll>(k+1,0)));
    for(int i=1;i<=s.size();i++){
        for(int t=1;t<=s.size();t++){
            for(int h=0;h<=k;h++){
                dp[i][t][h]=max(dp[i-1][t][h],dp[i][t-1][h]);
                if(s[i-1]==s[s.size()-t]){
                    dp[i][t][h]=max(dp[i][t][h],dp[i-1][t-1][h]+1);
                    for(int w=0;w<26;w++){
                        dp[i][t][h]=max(dp[i][t][h],dp[back[i][w]][s.size()-next[s.size()-t][w]][h]+1);
                    }
                }
                if(h!=0){
                    dp[i][t][h]=max(dp[i][t][h],dp[i-1][t-1][h-1]+1);
                }
            }
        }
    }
    for(int i=0;i<=s.size();i++){
        for(int t=0;t<=s.size();t++){
            for(int h=0;h<=k;h++){
                if(i+t<=s.size()){ans=max(ans,dp[i][t][h]*2);}
                if(i+t==s.size()+1){ans=max(ans,dp[i][t][h]*2-1);}
            }
        }
    }
    cout<<ans<<endl;
    

    return 0;
}


Measured memory_bytes: 216960
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define itrep(i, a) for (auto i = (a).begin(); i != (a).end(); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()
#define mp(a, b) make_pair((a), (b))

using namespace std;

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

template<class T> void inputVector(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < v.size(); i++) cin >> v[i];
}

signed main() {
	string S;
	cin >> S;

	int N = S.size();

	if (S[0] == '0' || S[N - 1] == '1') {
		cout << -1 << endl;
		return 0;
	}

	rep(i, (N + 1) / 2) {
		if (S[i] != S[N - i - 2]) {
			cout << -1 << endl;
			return 0;
		}
	}

	vector<pair<int, int>> ret;

	ret.push_back(mp(1, 2));
	int now = 2;
	int next = 3;
	REP(i, 1, (N - 1) / 2) {
		if (S[i] == '1') {
			ret.push_back(mp(now, next));
			now = next;
			next++;
		} else {
			ret.push_back(mp(now, next));
			next++;
		}
	}

	while (ret.size() < N - 1) {
		ret.push_back(mp(now, next));
		next++;
	}

	for (auto &pr : ret) {
		cout << pr.first << " " << pr.second << endl;
	}

    return 0;
}


Measured memory_bytes: 3312
#include <bits/stdc++.h> 
using namespace std;
#define ll long long 
#define mod 1000000007
#define MOD 99824435300000000
inline ll mul(ll a,ll b){
  a=(a+MOD)%MOD;
  b=(b+MOD)%MOD;
  ll c=a*b;
  c=(c+MOD)%MOD;
  return c;
}
inline ll add(ll a,ll b){
  a=(a+MOD)%MOD;
  b=(b+MOD)%MOD;
  ll ans=(a+b);
  ans=(ans+MOD)%MOD;
  return ans;
}

ll power(ll a,ll b,ll c){
  ll ans=1;
  while(b){
    if(b&1){
      ans=mul(ans,a);
    }
    a=mul(a,a);
    b=b/2;
  }
  return ans;
}
inline ll max(ll a,ll b){return a>b?a:b;}
inline ll min(ll a,ll b){return a<b?a:b;}

ll f(int i,int j,vector<string>&v,int h,int w,vector<vector<ll> >&dp){
  if(i>=h||j>=w)return 0;
  if(dp[i][j]!=-1)return dp[i][j];
  if(v[i][j]=='#')return 0;
  if(i==h-1&&j==w-1)return 1;
  ll pp=f(i+1,j,v,h,w,dp);
  pp+=f(i,j+1,v,h,w,dp);
  return dp[i][j]=pp%mod;
}
int main()
{
  int h,w; cin>>h>>w;
  vector<string> v;
  for(int i=0;i<h;++i){
    string s; cin>>s;
    v.push_back(s);
  }
  vector<vector<ll> > dp(h+1,vector<ll>(w+1,-1));
  ll res=f(0,0,v,h,w,dp);
  cout<<res;
  return 0;
}

Measured memory_bytes: 9344
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int a[4];
	for(int i=0;i<4;i++)
		cin>>a[i];
	sort(a,a+4);
	if(a[0]==1&&a[1]==4&&a[2]==7&&a[3]==9)
		cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
} 

Measured memory_bytes: 256
//D
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
ll cnt[maxn];
int main(){
	int n,m,q;
	cin >> n;
	ll ans = 0;
	for(int i = 1;i <= n;i++){
		int x;
		cin >> x;
		cnt[x]++;
	}
	for(int i = 1;i < maxn;i++)ans += i*cnt[i];
	cin >> q;
	while(q--){
		int a,b;
		cin >> a >> b;
		ans -= cnt[a]*a;
//		cnt[b] = cnt[a];
		ans += b*cnt[a];
		cnt[b] += cnt[a];
		cnt[a] = 0;
		cout << ans << endl;
	}

	return 0;
}


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

int main() {
	int a, b, c, d, p;
	cin >> a >> b >> c >> d >> p;
	int x, y;
	x = p * a;
	if (p <= c) {
		y = b;
	}
	else {
		y = b + ((p - c) * d);
	}
	if (y > x) {
		cout << x << endl;
	}
	else {
		cout << y << endl;;
	}
	return 0;
}


Measured memory_bytes: 3088
#include <stdio.h>

int main(void){
  int a,b,c,x,y;
  int money,selectA,selectB;

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

  if(x>y){
    if(b+a>2*c){
      selectA=2*c*y+(x-y)*a;
      selectB=c*2*x;
      if(selectA>selectB){
        printf("%d\n",selectB);
      }else{
        printf("%d\n",selectA);
      }
    }
    else{
      money=a*x+b*y;
      printf("%d\n",money);
    }
    }else{
      if(b+a>2*c){
        selectA=2*c*x+(y-x)*b;
        selectB=c*2*y;
        if(selectA>selectB){
          printf("%d\n",selectB);
        }else{
          printf("%d\n",selectA);
        }
      }
      else{
        money=a*x+b*y;
        printf("%d\n",money);
      }
    }
  return 0;
}


Measured memory_bytes: 128
def main():
    N = int(input())
    S = input()
    
    ans = S.count('R') * S.count('G') * S.count('B')

    for i in range(N-2):
        for j in range(i+1, i+1+(N-1-i)//2):
            k = j + (j - i)
            if len(set([S[i], S[j], S[k]])) == 3:
                ans -= 1
            
    print(ans)


if __name__ == "__main__":
    main()

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

using namespace std;

#define FOR(i,s, t) for(int i = s; i < t; i++)
#define ALL(a)  a.begin(), a.end()
#define SZ(x) (int)x.size()
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define SORT(a) sort(ALL(a))
using VI = vector<int>;


int main() {

	int N, K; cin >> N;
	VI a(N);
	FOR(i, 0, N) {
		cin >> a[i];
	}
	VI b = a;
	SORT(a);
	int m1 = a[N / 2 - 1];
	int m2 = a[N / 2];

	FOR(i, 0, N) {
		cout << ((b[i] < m2) ? m2 : m1) << endl;
	}
	return 0;
}


Measured memory_bytes: 3712
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <chrono>

using namespace __gnu_pbds;
using namespace std;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)

#define ll long long int
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define pi pair<ll,ll>
#define pii pair<ll,pi >
#define ppi pair<pi,ll>
#define ppp pair<pi,pi >
#define ex(str,a,b) str.substr((int)(a),min((int)str.size()-a,(int)(b-a+1))) 
#define all(X) X.begin(),X.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// for pair comparison function(ascending order) use return (i1.ff < i2.ff);

/* string operations :
   str.substr (x,y) : returns a substring str[x],str[x+1],...str[x+y-1]
   __builtin_popcount(n) : no. of set bits in n.
*/

const int M = (1<<20)+5;
const int md = 1e9+7;

priority_queue<ll,vector<ll >,greater<ll > > pq;

ll pwr(ll a,ll n,ll m)
{
	ll p=1;
	while(n>0)
	{
		if(n%2==1)
			p=(p*a)%m;
		a=(a*a)%m;
		n=n/2;
	}
	return p;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll a,b;
	cin >> a >> b;
	cout << a*b << "\n";
}

Measured memory_bytes: 3644
#include <iostream>
#include <iomanip>
#include <math.h>
using namespace std;

int main(){
  int a,b;
  char op;
  while(1){
    cin >> a >> op >> b;

    if(op == '?')
      break;

    switch(op){
      case '+':
        cout << a+b << endl;
        break;
      case '-':
        cout << a-b << endl;
        break;
      case '*':
        cout << a*b << endl;
        break;
      case '/':
        cout << a/b << endl;
        break;
      }
  }

  return 0;
}



Measured memory_bytes: 3096
#![allow(unused_imports)]
#![allow(unused_variables)]
#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(deprecated)]

use std::cell::{Cell, Ref, RefCell, RefMut};
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::fmt::{Debug, Formatter, Write as FmtWrite};
use std::io::{stderr, stdin, BufRead, Write};
use std::mem::{replace, swap};
use std::ops::*;
use std::rc::Rc;
use std::usize;

const MOD_10_9_7: u64 = 1_000_000_007;
const INF: i64 = 1_000_000_000_000;
const MIN_INF: i64 = -1_000_000_000_000;

/// FYI: https://github.com/vain0x/scan-bench
#[allow(unused_macros)]
macro_rules! read {
    ([$t:ty] ; $n:expr) =>
        ((0..$n).map(|_| read!([$t])).collect::<Vec<_>>());
    ($($t:ty),+ ; $n:expr) =>
        ((0..$n).map(|_| read!($($t),+)).collect::<Vec<_>>());
    ([$t:ty]) =>
        (rl().split_whitespace().map(|w| w.parse().unwrap()).collect::<Vec<$t>>());
    ($t:ty) =>
        (rl().parse::<$t>().unwrap());
    ($($t:ty),*) => {{
        let buf = rl();
        let mut w = buf.split_whitespace();
        ($(w.next().unwrap().parse::<$t>().unwrap()),*)
    }};
}

fn rl() -> String {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    buf.trim_right().to_owned()
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

fn main() {
    let s: String = read!(String);
    let sc: Vec<char> = s.chars().collect();

    let mut cnt_a = 0;
    let mut ans = 0i64;
    let mut i = 0;
    while i < sc.len() - 1 {
        if sc[i] == 'A' {
            cnt_a += 1;
            i += 1;
        } else if sc[i] == 'B' && sc[i + 1] == 'C' {
            ans += cnt_a;
            i += 2;
        } else {
            cnt_a = 0;
            i += 1;
        }
    }
    println!("{}", ans);
}


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

ll modinv(ll a, ll m) {
  ll b=m, u=1, v=0;
  while(b) {
    ll t=a/b;
    a -= t*b; swap(a, b);
    u -= t*v; swap(u, v);
  }
  u %= m;
  if(u<0)
    u += m;
  return u;
}

ll cmb(int n, int r) {
    ll x=1,y=1;
    rep(i,r) {
        x *= n-i;
        x %= MOD;
        y *= r-i;
        y %= MOD;
    }

    return x * modinv(y, MOD) % MOD;
}

int main() {
    ll n,a,b,t,x=1,y,z;
    cin >> n >> a >> b;

    t = n/100000;
    if(t == 0) {
        rep(i,n) {
            x *= 2;
            x %= MOD;
        }
    } else {
        ll x1=1,x2=1,x3=1;
        rep(i,t) {
            x1 *= 2;
            x1 %= MOD;
        }
        rep(i,100000) {
            x3 *= x1;
            x3 %= MOD;
        }
        rep(i,n%100000) {
            x2 *= 2;
            x2 %= MOD;
        }
        x = (x3*x2)%MOD;
    }

    y = cmb(n,a);
    z = cmb(n,b);
    
    t = (x-y-z-1)%MOD;
    if(t < 0)
        t += MOD;
    cout << t << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int a[105];
int main(){
    int N, x;
    scanf("%d%d", &N, &x);
    for(int i = 1; i <= N; i++){
    	scanf("%d", &a[i]);
    }
    sort(a+1,a+N+1);
    int ans = 0;
    int rest = x;
    for(int i = 1; i <= N; i++){
    	if(a[i] <= rest && i != N){
    		rest -= a[i];
    		ans++;
    	}
    	if(i == N && rest == a[i])
    		ans++;
    }
    printf("%d\n", ans);
return 0;
}

Measured memory_bytes: 256