akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <vector>
#include <string.h>
#include <string>
#include <algorithm>
#include <math.h>
#include <functional>
#include <queue>
#include <set>
#include <map>

using namespace std;
typedef long long LL;
typedef pair<string, int> P;
const int MAXN = 305;
const int INF = 0x3f3f3f3f;
//const int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
const int dir[4] = { -1, 1, 4, -4 };

map<string, int> mp;
int ans;

void bfs() {
    string source = "01234567";
    queue<P> que;
    que.push(P(source, 0));
    mp[source] = 0;
    while (!que.empty()) {
        P p = que.front(); que.pop();
        string str = p.first;
        int pos = p.second;
        for (int i = 0; i < 4; ++i) {
            int npos = pos + dir[i];
            if (0 <= npos && npos < 8 && !(pos == 3 && npos == 4) && !(pos == 4 && npos == 3)) {
                string nstr = str;
                swap(nstr[npos], nstr[pos]);
                if (mp.find(nstr) == mp.end()) {
                    que.push(P(nstr, npos));
                    mp[nstr] = mp[str] + 1;
                }
            }
        }
    }
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    string maze;
    bfs();
    while (getline(cin, maze)) {
        maze.erase(remove(maze.begin(), maze.end(), ' '), maze.end());
        ans = mp[maze];
        printf("%d\n", ans);
    }
    return 0;
}


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

int main(){
  ll N,K;cin >> N >> K;
  ll ans = 0;
  for(ll i=K;i<=N+1;i++){
    ll x = i*(N+1-i) + 1;
    x %= MOD;
    ans += x;
    ans %= MOD;
  }
  cout << ans << endl;
}

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

#define LL long long

const int N = 1020;
const long long mod = 998244353;

using namespace std;

LL n;

int main()
{
    ios_base::sync_with_stdio(0);
    //freopen( "input.txt" , "r" , stdin );
    //freopen( "output.txt" , "w" , stdout );

    cin>>n;
    cout<<3 * ( n * n );
}


Measured memory_bytes: 256
c = [list(map(int,input().split())), 
     list(map(int,input().split())), 
     list(map(int,input().split()))]
if c[0][0]-c[1][0] != c[0][1]-c[1][1] or c[0][1]-c[1][1] != c[0][2]-c[1][2]:
  print('No')
elif c[1][0]-c[2][0] != c[1][1]-c[2][1] or c[1][1]-c[2][1] != c[1][2]-c[2][2]:
  print('No')
else:
  print('Yes')

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

void trace(int A[], int N)
{
    for (int i = 0; i < N; i++ )
    {
       if (i > 0)
           cout << " ";
       cout << A[i];
    }
    cout << "\n";
}

void insertionSort(int A[], int N)
{
    int j, i, v;
    for (i = 1; i < N; i++)
    {
        v = A[i];
        j = i - 1;
        while ( j >= 0 && A[j] > v)
        {
            A[j + 1] = A[j];
            j--;
        }
        A[j + 1] = v;
        trace(A, N);
    }
}

int main()
{
    int N, i, j;
    int A[100];

    cin >> N;

    for (i = 0; i < N; i++)
        cin >> A[i];

    trace(A, N);
    insertionSort(A, N);

    return 0;
}


Measured memory_bytes: 3084
#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define rep(i,a) for(i = 0 ; i < a ; i++)
#define whln(t) while(t--)
#define whlp(t) while(t++)
#define ff first
#define ss second



int main(){
	#ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("output.txt", "w", stdout); 
	#endif
	char arr[4];

	cin>>arr;

	if(arr[1]=='B')
		cout<<"ARC\n";
	else 
		cout<<"ABC\n";


		
    //your code here
    return 0;
	
}

Measured memory_bytes: 3564
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
template<class T> void chmin(T& a,const T& b){if(a>b)a=b;}
template<class T> void chmax(T& a,const T& b){if(a<b)a=b;}
int N,K;
int V[55];
int rui[55];
int main(){
	cin >> N >> K;
	for(int i=0;i<N;i++)cin >> V[i];
	rui[0]=V[0];
	for(int i=1;i<N;i++)rui[i]=rui[i-1]+V[i];
	int ans = 0;
	for(int i=0;i<=min(K,N);i++){
		for(int l=0;l<=i;l++){
			vector<int> vec;
			for(int j=0;j<l;j++)vec.pb(V[j]);
			for(int j=0;j<i-l;j++)vec.pb(V[N-1-j]);
			sort(all(vec));
			int ig = K-i;
			int cnt=0;
			int sum = 0;
			for(int j=0;j<vec.size();j++){
				if(vec[j]<0&&cnt<ig){
					cnt++;
					continue;
				}
				sum += vec[j];
			}
			ans = max(ans,sum);
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
use proconio::*;
use std::process::exit;
use itertools::Itertools;

fn main() {
    input! {
    a:usize,
    b:usize,
    v:[String;a]
    }
    let v=v.iter().map(|a|a.chars().collect_vec()).collect_vec();
    for i in 0..a {
        for j in 0..b {
            if v[i][j]=='#'{
                if !(i>0&&v[i-1][j]=='#')&&!(i<a-1&&v[i+1][j]=='#')&&!(j>0&&v[i][j-1]=='#')&&!(j<b-1&&v[i][j+1]=='#'){
                    println!("No");
                    exit(0);
                }
            }
        }
    }
    println!("Yes");
}

Measured memory_bytes: 2180
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Main p = new Main();
	}

	public Main() {
		Scanner sc = new Scanner(System.in);
		int n =sc.nextInt();
		for(int i=0;i<n;i++){
			String s = sc.next();
			solve(s);
		}
		
	}

	public void solve(String s) {
		System.out.println(rec(s));
	}

	private int rec(String s) {
		if(s.indexOf(']') == s.length()-1)
			return Integer.parseInt(s.substring(1, s.length()-1))/2+1;
		
		int last = 0;
		int cur = 0;
		
		ArrayList<Integer> l = new ArrayList<Integer>(); 
		for(int i=1;i<s.length()-1;i++){
			if(s.charAt(i)=='[')
				cur++;
			else if(s.charAt(i)==']')
				cur--;
			
			if(cur==0){
				l.add(rec(s.substring(last+1, i+1)));
				last = i;
			}
		}
		
		Collections.sort(l);
		int ret = 0;
		for(int i=0;i<l.size()/2+1;i++)
			ret += l.get(i);
//		System.out.println(s+" "+ret+" "+l.size());
		return ret;
	}

}

Measured memory_bytes: 40876
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
typedef int64_t ll;

int main(){
  int n,d;
  cin>>n>>d;
  atcoder::two_sat ts(n);
  ll x[n],y[n];
  for(int i=0;i<n;i++)cin>>x[i]>>y[i];
  for(int i=0;i<n-1;i++){
    for(int j=i+1;j<n;j++){
      if(abs(x[i]-x[j])<d)ts.add_clause(i,false,j,false);
      if(abs(x[i]-y[j])<d)ts.add_clause(i,false,j,true);
      if(abs(y[i]-x[j])<d)ts.add_clause(i,true,j,false);
      if(abs(y[i]-y[j])<d)ts.add_clause(i,true,j,true);
    }
  }
  cout<<(ts.satisfiable() ? "Yes" : "No")<<endl;
  if(ts.satisfiable()){
    vector<bool> ans=ts.answer();
    for(int i=0;i<n;i++){
      if(ans[i])cout<<x[i]<<endl;
      else cout<<y[i]<<endl;
    }
  }
}


Measured memory_bytes: 3760
#include<bits/stdc++.h>
#define ULL unsigned long long
#define LL long long
#define Max 100005
#define mem(a,b) memset(a,b,sizeof(a));
#define pb push_back
#define mp make_pair
const LL mod=1e9+7;
const ULL base=131;
const LL LL_MAX=9223372036854775807;
using namespace std;
int main()
{
    int n,d;
    scanf("%d%d",&n,&d);
    printf("%d\n",n/(2*d+1)+(n%(2*d+1)==0?0:1));
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000000;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

//gcd,lcm,べき,二進展開
//組み合わせ、mod計算
//最短路問題、bit、union find

///////////////////////////



int main() {

	ll N, M;
	cin >> N >> M;

	ll p[MAX];
	string S[MAX];
	repn(i, M) cin >> p[i] >> S[i];

	ll ac[MAX] = {};
	ll wacount[MAX] = {};

	repn(i, M) {
		if (S[i] == "AC") { ac[p[i]] = 1; }
		else if (S[i] == "WA") { if (ac[p[i]] == 0) { wacount[p[i]]++; } }
	}

	ll se = 0;
	ll pen = 0;

	repn(i, N) {
		se += ac[i];
		if (ac[i] == 1) { pen += wacount[i]; }
	}

	cout << se << " " << pen;

	system("PAUSE");


}


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

int main(){
    int n; cin >> n;
    vector<int> v(n);
    double sum = 0;
    rep(i, n){
        cin >> v.at(i);
        sum += v.at(i);
    }
    int ave = round(sum / (double)n);
    int ans = 0;
    rep(i, n){
        ans = ans + pow(ave-v.at(i), 2);
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3680
N, F = map(int, input().split())
data = []
tmp = {}
for i in range(N) :
    data.append(list(input().split()))
    for x in range(1, len(data[i]) - 1) :
        for y in range(x+1, len(data[i])) :
            a = data[i][x]
            b = data[i][y]
            a, b = min(a, b), max(a, b)
            if (a, b) not in tmp :
                tmp[(a, b)] = 1
            else :
                tmp[(a, b)] += 1

ans = []
for k in tmp :
    if tmp[k] >= F :
        ans.append(list(k))

ans = sorted(ans, key = lambda x: x[1])
ans = sorted(ans)
print(len(ans))
if len(ans) != 0 :
    for i in range(len(ans)) :
        print(*ans[i])
            


Measured memory_bytes: 6724
N,K = map(int,input().split())
A = list(map(int,input().split()))

Ad = {x:0 for x in set(A)}
if len(set(A)) <= K:
    print(0)
else:
    count = 0
    for a in A:
        Ad[a] += 1
    Ad = sorted(Ad.items(), key=lambda x:x[1])
    for i in range(len(set(A))-K):
        count += Ad[i][1]
    print(count)

Measured memory_bytes: 52600
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define BUGAVOID(x) x
#define rep(...) BUGAVOID(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define sz(c) (int)(c.size())
#define all(c) c.begin(),c.end()
#define ms(a,v) memset(a,v,sizeof(a))
#define mp make_pair
#define write(x) cout<<(x)<<endl
using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vll;
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; }return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; }return 0; }
const int INF = 1 << 28; const ll LINF = 1ll << 60;
const int MAX = 1e5 + 5; const int MOD = 1e9 + 7; const double EPS = 1e-6;
const int dy[4] = { 0,1,0,-1 }; const int dx[4] = { 1,0,-1,0 };
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); }; }aaaa;

int N, M, C;
vi B;
vector<vector<int>> A;

int ans;
string s;

int main() {
    cin >> N >> M >> C;
    B.resize(M);
    rep(i, M) cin >> B[i];
    A.resize(N, vector<int>(M));
    rep(i, N) {
        rep(j, M) cin >> A[i][j];
    }
    
    ans = 0;
    rep(i, N) {
        ll score = 0;
        rep(j, M) {
            score += A[i][j] * B[j];
        }
        if (score + C > 0) ans++;
    }

    write(ans);


}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <cmath>
#include <limits>
#include <numeric>
#include <iomanip>
#include <cstdlib>
#include <iterator>
#include <functional>

using namespace std;

typedef unsigned                    ui;
typedef int                         si;
typedef long                        sl;
typedef long long                   ll;
typedef unsigned long long          ull;

#ifdef LOCALHOST
std::ifstream in("input.txt", std::ifstream::in);
#endif // LOCALHOST

#ifdef LOCALHOST
#define is in
#else
#define is cin
#endif // LOCALHOST

int main(int argc, char *argv[])
{
    std::ios_base::sync_with_stdio(false);

    ll n, k;
    cin >> n >> k;

    vector<ll> h(n, 0);
    for (int i = 0; i < n; ++i) {
        cin >> h[i];
    }

    vector<ll> dp(n, 0);
    dp[0] = 0;

    for (int i = 1; i < n; ++i) {
        ll min_weight = 1e18;
        for (int j = 1; j <= k && j <= i; ++j) {
            min_weight = min(min_weight, dp[i - j] + abs(h[i] - h[i - j]));
        }

        dp[i] = min_weight;
    }

    cout << dp[n - 1] << endl;

    return 0;
}


Measured memory_bytes: 1792
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <bitset>
#include <functional>
#include <numeric>
#include <ctime>
#include <cassert>
#include <cstring>
#include <fstream>

#define rep(i, a, b) for(int (i)=(a); (i)<(b); (i)++)
#define irep(i, a, b) for(int (i)=(a);(i)<=(b);(i)++)
#define rrep(i, a, b) for(int (i)=(a);(i)>=(b);(i)--)

using namespace std;

const int MOD = 1e9 + 7;
const long long INF = 1e18;

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

    long long sumx = accumulate(a.begin(), a.end(), 0LL);

    long long now = 0;
    long long minx = INF;

    rep(i, 0, n - 1) {
        now += a[i];
        minx = min(minx, abs(2 * now - sumx));
    }

    cout << minx << endl;
    return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int d = sc.nextInt();
        String a = sc.next();
        String[] b = a.split("");
        for (int i = 0; i < b.length; i++) {
            int c = b[i].charAt(0);
            String next = String.valueOf((char) (c + d));
            if ((c + d) > 90) {
                c = c + d - 26;
                next = String.valueOf((char) (c));
            }
            System.out.print(next);
        }
    }
}

Measured memory_bytes: 24788
#include<bits/stdc++.h>
using namespace std;
#define M 300005
int read() {
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
	{
	    if(ch=='-') w=-1;
	    ch=getchar();
	}
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s*w;
}
int n,p[M];
bool check(int s,int t) {
    int mn=1e9,mx=-1e9;
    for(int i=s;i<=t;i++)
	mx=max(mx,p[i]),mn=min(mn,p[i]);
    if(mn!=s||mx!=t) return 0;
    int sub_mx=-1e9;
    mx=-1e9;
    for(int i=s;i<=t;i+=2)
	if(p[i]>mx) mx=p[i];
	else if(p[i]>sub_mx) sub_mx=p[i];
	else return 0;
    return 1;
}
void work() {
    for(int i=1;i<=n;i++)
	{
	    if(p[i]==i) continue ;
	    int s=i,t;
	    for(t=i;t<=n-2;t+=2)
		if(p[t+1]!=t+1||p[t+2]==t+2) break ;
	    if(!check(s,t)) {cout<<"No"<<'\n';return ;}
	    i=t;
	}
    cout<<"Yes"<<'\n';
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++) p[i]=read();
    work();
    return 0;
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N,top=0,tairyoku=0,saisyou=2000000;
    cin >> N;
    int X[N];
    for(int i=0;i<N;i++){
        cin >> X[i];
        if(X[i] > top) top = X[i];
    }
    for(int i=0;i<=top;i++){
        tairyoku=0;
        for(int j=0;j<N;j++){
            tairyoku+=(X[j]-i)*(X[j]-i);
        }
        if(saisyou>tairyoku)saisyou=tairyoku;
    }
    cout << saisyou;
}

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

using ll = long long int;

int main()
{
    ll x;
    cin>>x;
    ll steps=0;
    ll p=100;
    while(p<x)
    {
        p=floor(1.01*p);
        steps+=1;
    }
    cout<<steps<<endl;
}


Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long int
int main(){
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
	fastio
	ll n;
	cin>>n;
	ll cnt=1,ans=0;
	while(n>0){
		ans+=cnt;
		cnt*=2;
		n/=2;
	}
	cout<<ans;
	return 0;
}

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

int main(){
    int N;
    cin>>N;
    
    vector<bool> v(N+1);
    vector<int> numbers(N+1);
    for(int i=1; i<=N; i++){
        int num;
        cin>>num;
        numbers[i] = num;
        if(i==num){
            v[i] = true;
        }else{
            v[i] = false;
        }
    }

    int cnt = 0;
    for(int i=1; i<N; i++){
        if(v[i] && v[i+1]){
            v[i] = false;
            v[i+1] = false;
            cnt++;
 
        }else if(v[i] && !v[i+1]){
 
            v[i] = false;
            v[i+1] = false;       
       

            if(numbers[i] == i){
                v[i] = true;
            }
            if(numbers[i+1] == i+1){
                v[i+1] = true;
            }
            cnt++;
            
        }
    }
    if(v[N]){
        cnt++;
    }
    cout<< cnt <<endl;
    return 0;
}

Measured memory_bytes: 3720
import java.util.Scanner;

class Main{

    public static void main(String args[]){
	Scanner scan = new Scanner(System.in);
	int a =	scan.nextInt();
	int b =	scan.nextInt();
	int c =	scan.nextInt();
	if(b-a == c-b){
	    System.out.println("YES");
	}else{
            System.out.println("NO");
	}
    }
}

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

using ll = long long;

template<typename T>
T gcd(T a, T b)
{
	if (a < b)	return gcd(b, a);
	T r;
	while ((r = a % b))
	{
		a = b;
		b = r;
	}
	return b;
}

template<typename T>
T lcm(T a, T b)
{
	return a * b / gcd(a, b);
}

template<typename T>
T ext_gcd(T a, T b, T& x, T& y)
{
	x = 1;
	y = 0;
	T x0 = 0, y0 = 1;
	while (b != 0)
	{
		T q = a / b;
		a -= q * b;
		swap(a, b);
		x -= q * x0;
		swap(x, x0);
		y -= q * y0;
		swap(y, y0);
	}
	return a;
}

template<typename T>
T inv_mod(T a, T mod)
{
	T t1, t2;
	ext_gcd(a, mod, t1, t2);
	t1 %= mod;
	if (t1 < 0)		t1 += mod;
	return t1;
}

template<typename T>
T combination_large(T n, T k, T mod)
{
	if (n < k || n < 0 || k < 0)	return 0;
	vector<T> inv(n + 1, 1), fact(n + 1, 1), fact_inv(n + 1, 1);
	for (T i = 2; i <= n; ++i)
	{
		inv[i] = mod - inv[mod % i] * (mod / i) % mod;
		fact[i] = (fact[i - 1] * i) % mod;
		fact_inv[i] = fact_inv[i - 1] * inv[i] % mod;
	}
	return fact[n] * (fact_inv[k] * fact_inv[n - k] % mod) % mod;
}

template<typename T>
T combination(T n, T k, T mod = 1)
{
	vector<vector<T>> table(n + 1, vector<T>(k + 1, 1));
	for (T i = 1; i <= n; ++i)
	{
		table[i][0] = 1;
		for (T j = 1; j <= n; ++j)
		{
			table[i][j] = (table[i - 1][j - 1] + table[i - 1][j]) % mod;
		}
	}
}


int main(int, char**)
{
	long long N;
	scanf("%lld",&N);
	std::vector<long long> X(N);
	for(int i = 0 ; i < N ; i++){
		scanf("%lld",&X[i]);
	}

	ll c = 0;
	for (ll i = 0; i < N; ++i)
	{
		c += X[i];
	}
	c /= N;
	ll sum1 = 0;
	ll sum2 = 0;
	for (ll i = 0; i < N; ++i)
	{
		sum1 += (X[i] - c) * (X[i] - c);
		sum2 += (X[i] - (c + 1)) * (X[i] - (c + 1));
	}
	cout << min(sum1, sum2) << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define MAX 100
#define WHITE 0
#define BLACK 1
#define INFTY 2001

// グラフの頂点数
int n;
// 隣接行列
vector<vector<int> > M(MAX, vector<int>(MAX));
// 頂点の状態を表す配列
vector<int> color(MAX, WHITE);
// d[v]はvとTの頂点を結ぶ辺の重みの最小値
vector<int> d(MAX, INFTY);
// p[v]はd[v]の重みを持つ辺のvでない方の頂点
vector<int> p(MAX, -1);

int mst()
{
  // 初期化
  int ans = 0;
  d.at(0) = 0;

  while (1)
  {
    // d[u]が最小であるようなV-Tの頂点uを選ぶ
    int u;
    int m = INFTY;
    for (int i = 0; i < n; i++)
    {
      if (color.at(i) != BLACK && d.at(i) < m)
      {
        m = d.at(i);
        u = i;
      }
    }

    if (m == INFTY)
    {
      // MNTが完成したとき
      break;
    }

    // uをTに追加する
    color.at(u) = BLACK;
    // uをTに追加したときの辺の重みをansに足す
    if (p.at(u) != -1)
    {
      ans += M.at(p.at(u)).at(u);
    }

    // uと隣接しているV-Tの各頂点iのd[i]を更新する
    for (int i = 0; i < n; i++)
    {
      if (color.at(i) != BLACK && M.at(u).at(i) != -1 && M.at(u).at(i) < d.at(i))
      {
        d.at(i) = M.at(u).at(i);
        p.at(i) = u;
      }
    }
  }

  return ans;
}

int main()
{
  // 入力
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      cin >> M.at(i).at(j);
    }
  }

  // 処理と出力
  cout << mst() << endl;
}


Measured memory_bytes: 3212
import heapq

cnt, ticket = map(int, input().split())
lst = list(map(lambda i:int(i) * (-1) , input().split()))
heapq.heapify(lst)

for _ in range(ticket):
  tmp_min = heapq.heappop(lst)
  heapq.heappush(lst, (-1) * (-tmp_min//2))
  
print(-sum(lst))

Measured memory_bytes: 14188
from itertools import permutations
n,m = map(int,input().split())
edge = [[0]*n for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a-=1; b-=1
    edge[a][b] = edge[b][a] = 1
ret = 0
for i in permutations(range(n)):
    if i[0] != 0 : break
    for j in range(n-1):
        if edge[i[j]][i[j+1]] == 0: break
    else:
        ret += 1
print(ret)


Measured memory_bytes: 3188
#include <stdio.h>

int main(void)
{
    int N;
    scanf("%d",&N);
    int a[N];
    for(int i=0;i<N;i++){
        scanf("%d",&a[i]);
    }
    int tmp;
    for(int s=0;s<N-1;s++){
        for(int t=s+1;t<N;t++){
            if(a[s]<a[t]){
                tmp=a[t];
                a[t]=a[s];
                a[s]=tmp;
            }
        }
    }
    int sum_a=0;
    int sum_b=0;
    for(int i=0;i<N;i++){
        if(i%2==0)
            sum_a+=a[i];
        else
            sum_b+=a[i];
    }
    int ans=sum_a-sum_b;
    printf("%d\n",ans);
    
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#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;

string S[30][30];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int H, W; cin >> H >> W;
	rep (i, H) rep (j, W) cin >> S[i][j];

	int res = -1;
	rep (i, H){
		rep (j, W){
			if (S[i][j] == "snuke"){
				res = W*i + j;
				break;
			} // end if
		} // end rep
		if (res != -1) break;
	} // end rep
	
	char col = (char)((res % W) + 'A');
	int  row = (res / W) + 1;	
	cout << col << row << endl;

	return 0;
}

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

using namespace std;

int main() {

	int n;
	cin >> n;
	if (n == 1) {
		cout << "Hello World" << endl;
	}
	else if (n == 2) {
		int a, b;
		cin >> a >> b;
		cout << a + b << endl;

	}




}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
#define pai 3.141592653589793238462643383279




int main(){
  int keta=-1; ll pow[11]; pow[0] = 1;
  rep(i, 10){
    pow[i+1] = pow[i]*10;
  }
  for(int i=0; i<=10; i++){
    cout << "? " << flush;
    cout << pow[i] << flush;
    cout << endl << flush;
    char c; cin >> c;
    if(c=='N'){
      keta = i; break;
    }
  }
  if(keta==-1){
    for(int i=0; i<=10; i++){
      cout << "? " << flush;
      cout << (ll)2LL*pow[i] << endl << flush;
      char c; cin >> c;
      if(c=='Y'){
        cout << "! " << pow[i] << endl << flush; return 0;
      }
    }
  }
  vector<int> made;
  for(int i=1; i<=keta; i++){
    ll ng = -1, ok = 9;
    if(i==1) ng = 0;
    while(abs(ok-ng)>1){
      ll mid = (ok+ng)/2;
      cout << "? " << flush;
      for(auto k: made){
        cout << k << flush;
      }
      cout << mid << flush;
      rep(i, keta-made.size()){
        cout << 9 << flush;
      }
      cout << endl;
      cout << flush;
      char c; cin >> c;
      if(c=='Y') ok = mid;
      else ng = mid;
    }
    made.push_back(ok);
  }
  cout << "! " << flush;
  for(auto k: made){
    cout << k << flush;
  }
  cout << endl; cout << flush; return 0;
}

Measured memory_bytes: 3712
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))


def main():
    s = input().strip()
    t = input().strip()
    accs, acct = [0], [0]
    for i in range(len(s)):
        if s[i] == "A":
            accs.append(accs[-1]+1)
        else:
            accs.append(accs[-1]+2)
    for i in range(len(t)):
        if t[i] == "A":
            acct.append(acct[-1]+1)
        else:
            acct.append(acct[-1]+2)
    q = int(input())
    for _ in range(q):
        a, b, c, d = map(int, input().split())
        if (accs[b]-accs[a-1])%3 == (acct[d]-acct[c-1])%3:
            print("YES")
        else:
            print("NO")


if __name__ == '__main__':
    main()


Measured memory_bytes: 53896
n,k = map(int,input().split())
s= input()
if n==1:
    print(1)
    exit()

ls = []
cnt=[0,0]
prev=int(s[0])
if prev==0:
    ls.append(0)
cnt[prev]+=1
for i in range(1,n):
    now= int(s[i])
    cnt[now] +=1
    if now!=prev:
        ls.append(cnt[prev])
        cnt[prev]=0
    prev = now
if cnt[now]!=0:
    ls.append(cnt[now])
if s[-1] =="0":
    ls.append((0))

##ls --> 1010..101の順

l=len(ls)//2+1
p = 0
idx = 0
ans =ls[0]
temp=ls[0]
for i in range(1,l):
    temp+= ls[2*i]+ls[2*i-1]
    ans = max(temp,ans)
    p+=1
    if p>=k:
        temp -= (ls[2*idx]+ls[2*idx+1])
        idx+=1
print(ans)


Measured memory_bytes: 4084
#include <iostream>

int main(){
	int n;
	std::cin >> n;
	while(n--){
		std::string sn, res = "";
		std::cin >> sn;

		//Type A
		//ªª>'CKöª~C©Â¨ ÌªªïÅ é
		if(sn.substr(0,2) == ">'" &&
			 sn[sn.size()-1] == '~' && (sn.size()-3) % 2 == 1){
			std::string st = sn.substr(2,sn.size()-3);
			//¨ Ì^ñª#
			if(st[st.size()/2] == '#'){
				st.replace(st.size()/2,1,"");
				
				//#ÈOª·×Ä=
				// int eq = 1;
				// for(int i=0;i<st.size();i++){
				// 	if(st[i] != '='){eq = 0;break;}
				// }
				// if(eq)std::cout << "A" << std::endl;
				if(st != ""){
					int pos;
					while(pos = st.find("="), pos != std::string::npos){
						st.replace(pos,1,"");
					}
					if(st == "")res = "A\n";
				}
			}
		}

		//Type B
		if(sn.substr(0,2) == ">^" &&
			 sn.substr(sn.size()-2,2) == "~~" &&
			 (sn.size()-4) % 2 == 0){
			std::string st = sn.substr(2,sn.size()-4);
			if(st != ""){
				int pos;
				while(pos = st.find("Q="), pos != std::string::npos){
					st.replace(pos,2,"");
				}
				if(st == "")res = "B\n";
			}
		}

		if(res == "")res = "NA\n";
		std::cout << res;
	}
}

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

using namespace std;
#define INF (1 <<29)

int N, M, R;
int d[201][201];
int r[9];
int A, B, C;
int res;
bool used[9];

void dfs(int c, int las, int dist) {
    if (c == R + 1) {
        if (res > dist) res = dist;
        return;
    }
    for (int i = 1; i <= R; i++)
        if (!used[i]) {
            used[i] = true;
            if (las == -1) dfs(c + 1, i, 0);
            else dfs(c + 1, i, dist + d[r[las]][r[i]]);
            used[i] = false;
        }
}

int main() {
    scanf("%d%d%d", &N, &M, &R);
    for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) if (i != j) d[i][j] = INF;
    for (int i = 1; i <= R; i++) scanf("%d ", &r[i]);
    for (int i = 1; i <= M; i++) {
        scanf("%d%d%d", &A, &B, &C);
        if (d[A][B] > C) d[A][B] = d[B][A] = C;
    }
    for (int k = 1; k <= N; k++)
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++)
                if (d[i][j] > d[i][k] + d[k][j])
                    d[i][j] = d[i][k] + d[k][j];
    res = INF;
    dfs(1, -1, 0);
    printf(" % d\n ", res);
}


Measured memory_bytes: 384
n = int(input())
x = [int(i) for i in input().split()]
loss = 0xFFFFFFFF

for i in range(100):
    hp = 0
    point = i
    for j in x:
        hp += (j - point) ** 2
        if loss < hp:
            break
    else:
        loss = hp
print(loss)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;

int64_t dfs(const vector<vector<int64_t>>& links, const vector<int64_t>& a, int64_t current, int64_t parent) {
  if (links[current].size() == 1 && parent >= 0) {
    return a[current];
  }

  int64_t s = 0;
  int64_t m = 0;
  for (auto v : links[current]) {
    if (v == parent) {
      continue;
    }
    auto tmp = dfs(links, a, v, current);
    if (tmp < 0) {
      return -1;
    }
    
    m = max(m, tmp);
    s += tmp;
  }
  
  
  
  int64_t l = a[current];
  int64_t k = s - l;
  if (k < 0 || k > l || 2 * k > s) {
    return -1;
  }
  
  if (m >= s - m) {
    if (k <= s - m) {
      return l - k;
    } else {
      return -1;
    }
  } else {
    if (k <= s / 2) {
      return l - k;
    } else {
      return -1;
    }
  }
}

main() {
  int64_t n;
  cin >> n;
  
  vector<int64_t> a(n);
  for (auto&& aa : a) {
    cin >> aa;
  }
  
  vector<vector<int64_t>> links(n);
  for (auto _ : irange(0L, n - 1)) {
    int64_t x, y;
    cin >> x >> y;
    --x;
    --y;
    links[x].push_back(y);
    links[y].push_back(x);
  }
  
  auto ret = dfs(links, a, 0, -1);
  cerr << ret << endl;
  if (ret < 0 || (ret != 0 && links[0].size() > 1)) {
    cout << "NO" << endl;
  } else {
    cout << "YES" << endl;
  }  
}

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

#define rep(i,n) for(ll i=0;i<(n);++i)
using ll = int_fast64_t;
using pll = pair<ll,ll>;
constexpr ll INF = (1LL<<60);
constexpr ll MOD = (1e9+7);
//constexpr ll MOD = (998244353);
template<class T> bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T> bool chmin(T &a,const T &b){if(a>b){a=b;return 1;}return 0;}
#if loc||local
void dump(){cerr<<endl;}
template<class T,class... Ts> void dump(T&& h, Ts&&... t){cerr<<h<<", ";dump(forward<Ts>(t)...);}
#else
void dump(){}
template<class T,class... Ts> void dump(T&& h, Ts&&... t){}
#endif
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<class T> ostream &operator<<(ostream& os,vector<T>const& v){for(auto const& vi:v)os<<vi<<" ";return os;}
template<class T,class U> ostream &operator<<(ostream& os,pair<T,U>const& p){os<<p.first<<","<<p.second;return os;}
template<class T>vector<T> vec(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto vec(size_t a, Ts... ts){return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...));}

signed main(){

  int n,x,y;
  cin>>n>>x>>y;
  x--;y--;

  vector<ll> ans(n);

  auto solve = [&](int s){
    vector<ll> dist(n,INF);
    priority_queue<pll,vector<pll>,greater<>> que;
    que.emplace(s,0);
    while(!que.empty()){
      pll v = que.top();
      que.pop();
      if(!chmin(dist[v.first],v.second))continue;
      if(v.first==x)que.emplace(y,v.second+1);
      if(v.first+1<n)que.emplace(v.first+1,v.second+1);
      if(v.first-1>=0)que.emplace(v.first-1,v.second+1);
    }
    dump(dist);
    for(int i=s+1;i<n;++i)ans[dist[i]]++;
  };

  rep(i,n)solve(i);
  for(int i=1;i<n;++i)cout<<ans[i]<<endl;

}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return 1;
    }
    return 0;
}
typedef long long int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define MOD (1000000007)
#define ALL(v) (v).begin(), (v).end()
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

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

int cnt(map<ll, int> &mp, int p)
{
    int ans = 0;
    for (auto e : mp)
    {
        if (e.second >= p)
        {
            ans++;
        }
    }
    return ans;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    ll ans = 0;

    map<ll, int> soinsu;

    for (ll num = 2; num <= n; num++)
    {
        ll rec = num;
        for (ll i = 2; i * i <= rec; i++)
        {
            while (rec % i == 0)
            {
                soinsu[i]++;
                rec /= i;
            }
        }
        if (rec != 1)
        {
            soinsu[rec]++;
        }
    }

    // p^4*q^4*r^2
    int tmp = cnt(soinsu, 4);
    ans += (tmp * (tmp - 1) / 2) * (cnt(soinsu, 2) - 2);
    // p^74
    ans += cnt(soinsu, 74);
    //p^24*q^2
    tmp = cnt(soinsu, 24);
    ans += tmp * (cnt(soinsu, 2) - 1);
    //p^14*q^4
    tmp = cnt(soinsu, 14);
    ans += tmp * (cnt(soinsu, 4) - 1);

    cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string.h>
#include<string>
#include<stack>
#include<stdlib.h>
#include<algorithm>
#include<utility>
using namespace std;
int main(){
	int a,b,c,d;
	cin>>a;
	b=a/100;
	c=(a-b*100)/10;
	d=(a-b*100-c*10);
	cout<<10-b<<10-c<<10-d<<endl;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vll = vector<long long>;
using vvi = vector<vector<int>>;
using pii = pair<int,int>;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define pb push_back

int cnt=0;
vector<vector<int>> G(2e5);
vector<int> seen(2e5,false);

void dfs(int u) {
  seen[u]=true;
  for(int next:G[u]) if(seen[next]==false) dfs(next);
}

int main() {
  int n,m; cin>>n>>m;
  int a,b,ans=0;
  for(int i=0;i<m;i++) {
    cin>>a>>b;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  for(int i=1;i<=n;i++) {
    if(seen[i]==false) {
      cnt++;
      dfs(i);
    }
  }
  cout<<cnt-1<<endl;
}


Measured memory_bytes: 12220
import java.util.Scanner;

public class Main {
    private static int MOD = 1000000007;

    public static void main(final String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final int x = scanner.nextInt();
        final int y = scanner.nextInt();

        final int a = Math.max(x, y);
        final int b = Math.min(x, y);

        int right = a / 2;
        int under = a % 2;

        boolean hit = false;
        while (right >= 0) {
            if (right * 2 + under == a && right + under * 2 == b) {
                hit = true;
                break;
            }

            right--;
            under += 2;
        }

        if (!hit) {
            System.out.println(0);
            return;
        }

        System.out.println(new CombinationCalculator(1000000,MOD).init().calc(right+under,Math.min(right,under)));
    }

    private static long originalPow(final long a, final int b) {
        long result = 1;
        for (int i = 0; i < b; i++) {
            result *= a;
            result %= MOD;
        }

        return result;
    }
    private static class CombinationCalculator {
        private final int size;
        private final int mod;
        private final long[] fac;
        private final long[] inv;
        private final long[] finv;

        CombinationCalculator(final int size, final int mod) {
            this.size = size;
            this.mod = mod;
            this.fac = new long[size];
            this.inv = new long[size];
            this.finv = new long[size];
        }

        CombinationCalculator init() {
            fac[0] = 1;
            fac[1] = 1;
            finv[0] = 1;
            finv[1] = 1;
            inv[1] = 1;
            for (int i = 2; i < size; i++) {
                fac[i] = fac[i - 1] * i % mod;
                inv[i] = mod - inv[mod % i] * (mod / i) % mod;
                finv[i] = finv[i - 1] * inv[i] % mod;
            }
            return this;
        }

        long calc(final int n, final int k) {
            return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
        }
    }
}


Measured memory_bytes: 48468
n,m=map(int,input().split())
a=[0]*n
b=[0]*n
for i in range(m):
    x,y=map(int,input().split())
    if x==1:
        a[y-1]+=1
    if y==n:
        b[x-1]+=1
ans='IMPOSSIBLE'
for i in range(n):
    if a[i]*b[i]>0:
        ans='POSSIBLE'
        break
print(ans)

Measured memory_bytes: 6132
import java.io.*;

public class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String input = br.readLine();
    String[] param = input.split(" ");
    int a = Integer.parseInt(param[0]);
    int b = Integer.parseInt(param[1]);
    int s = a * b;
    int l = (a + b) * 2;
    System.out.println(s + " " + l);
  }
}

Measured memory_bytes: 24200
import qualified Data.ByteString.Char8 as C
import Data.Maybe ( fromJust )

readInts :: IO [Int]
readInts = map (fst . fromJust . C.readInt) . C.words <$> C.getLine

main :: IO ()
main = do
  [k, s] <- readInts
  print $ f k s

numbers
  :: Int -> Int -> Int
numbers k = length . numbers' k 

numbers' :: Int -> Int -> [(Int,Int,Int)]
numbers' k s 
  = [ (x,y,z) | x <- [0..k]
              , y <- [0..k]
              , let z = s - x - y
              , 0 <= z && z <= k
              ]

-- https://atcoder.jp/contests/abc051/submissions/1127311
f :: Int -> Int -> Int
f k s = length [(x,y,z) | let m = max 0 (s-2*k)
                        , x <- [m .. k]
                        , y <- [m .. min k (s-x)]
                        , let z = s-x-y
                        , 0 <= z && z <= k
                        ]


Measured memory_bytes: 508
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f
 
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
   
using namespace std;
   
typedef long long ll;
typedef pair <double,double> P;
typedef pair <int,P> PP;
   
static const double EPS = 1e-12;
   
static const int tx[] = {0,1,0,-1};
static const int ty[] = {-1,0,1,0};

int main(){
  int num_of_problems;

  while(~scanf("%d",&num_of_problems)){
    vector<ll> problems;
    for(int problem_i = 0; problem_i < num_of_problems; problem_i++){
      ll problem;
      scanf("%lld",&problem);
      problems.push_back(problem);
    }
    ll sum[300001] = {};
    sort(problems.begin(),problems.end());
    for(int problem_i = 0; problem_i < num_of_problems; problem_i++){
      sum[problem_i + 1] += sum[problem_i] + problems[problem_i];
    }

    int num_of_participants;
    scanf("%d",&num_of_participants);

    ll abilities[300000];
    for(int participant_i = 0; participant_i < num_of_participants; participant_i++){
      ll ability;
      scanf("%lld",&ability);
      abilities[participant_i] = ability;
    }

    ll targets[300000];
    for(int participant_i = 0; participant_i < num_of_participants; participant_i++){
      ll target;
      scanf("%lld",&target);
      targets[participant_i] = target;
    }
    for(int participant_i = 0; participant_i < num_of_participants; participant_i++){
      int solved = upper_bound(problems.begin(),problems.end(),abilities[participant_i]) - problems.begin();
      printf("%s\n",(sum[solved] >= targets[participant_i]) ? "Yes" : "No");
    }
  }
}

Measured memory_bytes: 11352
#include <stdio.h>
 
int main(void)
{
  int num1;
  char op;
  int num3;
  
  scanf("%d %c %d",&num1,&op,&num3);
  
  if(op=='+'){
    printf("%d\n",num1+num3);
  }
  else if(op=='-'){
    printf("%d\n",num1-num3);
  }
  
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define sz(v) (int)(v).size()
#define pb push_back
#define sc second
#define fr first
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
using namespace std;
typedef long long int ll;
typedef pair <int, int> P;
const int MAX_N=1<<20;
int n,SIZE;
ll dat[MAX_N-1];
//初期化
void init(int n_){
    //要素数を2べきに
    SIZE=1;
    while(SIZE<n_) SIZE*=2;
    
    //全ての値をI_MAXに
    rep(i,0,2*SIZE-1) dat[i]=0;
}

//k番目の値(0-indexed)をaに変更
void update(int k, ll a){
    //葉の節点
    k+=SIZE-1;
    dat[k]=a;
    //登りながら更新
    while(k>0){
        k=(k-1)/2;
        dat[k]=max(dat[k*2+1],dat[k*2+2]);
    }
}
//開区間に注意
//[a,b)の最小値を求める
//後ろの方の引数は計算の簡単のための引数
//kは節点の番号、l,rはその節点が[l,r)に対応づいていることを表す
//従って、外からはquery(a,b,0,0,n)として呼ぶ
ll query(int a, int b, int k, int l, int r){
    //[a,b)と[l,r)が交差しなければ、I_MAX
    if(r<=a||b<=l) return 0;
    //[a,b)が[l,r)を完全に含んでいれば、この節点の値
    if(a<=l&&r<=b) return dat[k];
    else{
        //そうでなければ二つの子の最小値
        ll vl=query(a,b,k*2+1,l,(l+r)/2);
        ll vr=query(a,b,k*2+2,(l+r)/2,r);
        return max(vl,vr);
    }
}
ll dp[200000];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    int h[n];
    ll a[n];
    P m[n];
    rep(i,0,n) {
        cin>>h[i];
        m[i]=P(h[i],i);
    }
    rep(i,0,n) cin>>a[i];
    sort(m,m+n);
    init(n);
    dp[m[0].sc]=a[m[0].sc];
    update(m[0].sc,a[m[0].sc]);
    rep(i,1,n){
        dp[m[i].sc]=query(0,m[i].sc+1,0,0,SIZE)+a[m[i].sc];
        update(m[i].sc,dp[m[i].sc]);
    }
    ll ans=0;
    rep(i,0,n){
        ans=max(ans,dp[i]);
    }
    cout <<ans<<"\n";
}

Measured memory_bytes: 10368
import java.util.*;

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

class Solve{
	Solve(){}
	
	Scanner in = new Scanner(System.in);

	void solve(){
		int n = in.nextInt(), m = in.nextInt();
		String s[] = new String[n];
		for(int i = 0; i < n; i++) s[i] = in.next();
		for(int i = 0; i < n; i++){
			int c = -1;
			for(int j = 0; j < m; j++){
				if(j != 0) System.out.print(" ");
				if(s[i].charAt(j) == 'c') c = j;
				if(c == -1) System.out.print(c);
				else System.out.print(j - c); 
			}
			System.out.println();
		}
	}

}

Measured memory_bytes: 35880
#include<iostream>
#include<string>
using namespace std;
int main() {
    int A, B, C;
    int X;
    cin >> A >> B >> C;
    cin >> X;
    int c = 0;
    for(int i = 0; i <= A; i++){
        for(int j = 0; j <= B; j++){
            for(int k = 0; k <= C; k++){
                int Y = 500*i + 100*j + 50* k;
                if(X == Y) c++;
            }
        }
    }
    cout << c << endl;
    return 0;
}

Measured memory_bytes: 3576
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]

if len(set([(x+y)%2 for x, y in xy])) > 1:
    print(-1)
    exit()

m = 0
d = []
if sum(xy[0])%2 == 0:
    m += 1
    d.append(1)
for i in range(39):
    m +=1
    d.append(2**i)
print(m)
print(' '.join(list(map(str, d))))

for x, y in xy:
    ans = ''
    for dd in d[::-1]:
        if y >= abs(x): # Up
            ans = 'U' + ans
            y -= dd
        elif y > x and y < -x: # Left
            ans = 'L' + ans
            x += dd
        elif y <= -abs(x): # Down
            ans = 'D' + ans
            y += dd
        else: # Right
            ans = 'R' + ans
            x -= dd
    print(ans)


Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
#define rep(i, a, n) for (ll i = (a); i < (n); i++)
#define debug(x) cerr << #x << ": " << x << endl;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

int main() {
    ll n;
    cin >> n;
    vector<ll> d(n);
    rep(i, 0, n) cin >> d[i];
    sort(d.begin(), d.end());
    cout << d[n/2] - d[n/2-1] << endl;
}

Measured memory_bytes: 1024
import java.util.*;
import java.io.PrintWriter;
import static java.lang.Integer.*;
import static java.lang.Long.*;
import static java.lang.Math.*;
import static java.lang.System.*;

public class Main {
	public static final int MOD = 1000000007;
	public static void main(String[] args) {
		int i,j;
		Scanner sc = new Scanner(in);
		char[] s = sc.next().toCharArray();
//		String s = sc.next();
		sc.close();
		out.println(s[0]>='a'&&s[0]<='z'?'a':'A');
	}
}


Measured memory_bytes: 26968
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <set>
#include <map>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;

int main(){
  int n;
  cin >> n;
  if(n>=1000){
    cout << "ABD" << endl;
  }else{
    cout << "ABC" << endl;
  }
  return 0;
}


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

const int INF = 2000000;
char fl[1010][1010];
int d[1010][1010];

int bfs(int sx, int sy, int gx, int gy, int mx, int my) {
	typedef pair<int, int>P;
	int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };

	for (int i = 0;i < mx;i++)
		for (int j = 0;j < my;j++)d[i][j] = INF;

	queue<P>que;
	que.push(P(sx, sy));
	d[sx][sy] = 0;

	while (que.size()) {
		P p = que.front();
		que.pop();

		if (p.first == gx&&p.second == gy)break;

		for (int i = 0;i < 4;i++) {
			int nx = p.first + dx[i], ny = p.second + dy[i];

			if (0 <= nx&&nx < mx && 0 <= ny&&ny < my&&fl[nx][ny] != 'X'&&d[nx][ny] == INF) {
				que.push(P(nx, ny));
				d[nx][ny] = d[p.first][p.second] + 1;
			}
		}
	}
	return d[gx][gy];
}

int main() {
	int h, w, n;
	cin >> h >> w >> n;
	int al = 0;
	for (int i = 0;i < h;i++) {
		for (int j = 0;j < w;j++) { cin >> fl[i][j]; 
		}
	}
	char a[10] = { 'S','1','2','3','4','5','6','7','8','9' };
	for (int i = 0;i < n;i++) {
		int sx, sy;
		int gx, gy;
		for (int j = 0;j < h;j++) {
			for (int k = 0;k < w;k++) {

				if (fl[j][k]== a[i]) {
					sx = j;
					sy = k;
				}
				if (fl[j][k]== a[i+1]) {
					gx = j;
					gy = k;
				}
			}
		}

		al += bfs(sx, sy, gx, gy,h,w);
	}
	
	cout << al << endl;
	getchar();
	getchar();
	return 0;
}

Measured memory_bytes: 7944
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO 自動生成されたメソッド・スタブ
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		
		String newStr = "";
		
		for(int i = input.length() - 1; i >= 0; i--){
			if(i % 2 == 1){
				continue;
			}
			String tmp1 = input.substring(0, i/2);
			String tmp2 = input.substring(i/2, i);
			
			//System.out.println("tmp1 "+ tmp1);
			//System.out.println("tmp2 "+ tmp2);
			
			if(tmp1.equals(tmp2)){
				newStr = new String(tmp1);
				break;
			}
		}
		
		System.out.println(newStr.length() * 2);

	}

}


Measured memory_bytes: 21204
var lines =[];
var readline = require("readline");
var rl = readline.createInterface({
  input:  process.stdin,
  output: process.stdout
});

rl.on('line',function(x){
  lines.push(x);
});

rl.on('close',function(){
  var s = Number(lines[0].split(" "));
  var a =[];
  var flag = false;
  var ite = 0;


  var n = s;
  while(1){
      a.push(n);
      ite++;

      if(n%2===0){n=n/2;}
      else{n=3*n+1;}

      a.forEach(function(x){
          if(x === n){flag=true;}
      });

      if(flag===true){break;}

  }
  console.log(ite+1);
});


Measured memory_bytes: 7756