akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		char[] s = sc.next().toCharArray();
		boolean t = true;
		for (int i = 0; i < s.length; i++) {
			if (a != i && s[i] == '-') {
				t = false;
				break;
			}
			if (a == i && s[i] != '-') {
				t = false;
				break;
			}
		}
		if (t) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}


Measured memory_bytes: 23124
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <numeric> //lcm
#include <iomanip> //double精度 setprecision

using namespace std;

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = n-1; i >= 0; --i)
#define rep1(i,n) for(int i = 1; i <= (n); ++i)
#define rrep1(i,n) for(int i = (n); i >= 1; --i)
#define REP(i,n,m) for(int i = (n); i < (m); ++i)
#define all(vec) (vec).begin(),(vec).end()

#define debug(vec) for(auto v : vec) cerr << v << " "; cerr << endl;
#define debug2D(vec2D, w) for(auto vec : vec2D) { for (auto v : vec) cerr << setw(w) << v << " "; cerr << endl; } 
#define debugP(vec) for(auto v : vec) cerr << "(" << v.first << "," << v.second << ") "; cerr << endl;
#define debug2DP(vec2D) for(auto vec : vec2D) { for (auto v : vec) cerr << "(" << v.first << "," << v.second << ") "; cerr << endl; } 

const char en = '\n';

typedef long long ll;

constexpr ll INF = 1000000000; //10^10
//const ll MOD = 998244353;
constexpr ll MOD = 1000000007;

typedef vector<vector<int>> Graph;
void add_edge(Graph& g, int from, int to, bool isDirected) {
	g[from].push_back(to);
	if (!isDirected) g[to].push_back(from);
}

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


int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	int n;
  cin >> n;
	vector<int> l(n);
  rep(i,n) {
	  cin >> l[i];
	}

	ll ans = 0;
	rep(i, n) REP(j, i, n) REP(k, j, n) {
	  if (l[i] == l[j] || l[j] == l[k] || l[i] == l[k]) continue;
		if (l[i] + l[j] > l[k] && l[j] + l[k] > l[i] && l[k] + l[i] > l[j]) { ans++; }
	}

	cout << ans << endl;

}


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

int main() {
  int N, K;
  int j = 1;
  cin >> N >> K;
  for (int i = 0; i < N; i++) {
    if (j * 2 > j + K) {
      j += K;
    }
    else {
      j *= 2;
    }
  }
  cout << j << endl;
}

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

const int maxn = 1e5+7;

int n;
int h[maxn];
int dp[maxn];

int main(int argc, char *argv[]) {  
	std::cin >> n;
	for (int i = 0; i < n; i++) {
		std::cin >> h[i];
	}
	dp[0] = 0;
	dp[1] = std::abs(h[1] - h[0]);
	for (int i = 2; i < n; i++) {
		dp[i] = std::min(dp[i-1] + std::abs(h[i]-h[i-1]), dp[i-2] + std::abs(h[i]-h[i-2]));
	}
	std::cout << dp[n-1] << '\n';
}

Measured memory_bytes: 1024
package main
import (
	"fmt"
	"sort"
)
func main() {
	var n, m, x, y, i int
	fmt.Scan(&n, &m, &x, &y)
	a:=make([]int, n)
	b:=make([]int, m)
	for i=0;i<n;i++{
		fmt.Scan(&a[i])
	}
	for i=0;i<m;i++{
		fmt.Scan(&b[i])
	}
	sort.Sort(sort.IntSlice(a))
	sort.Sort(sort.IntSlice(b))
	for i=-100;i<=100;i++{
		if a[n-1]<i&&b[0]>=i&&i>x&&i<=y{
			fmt.Println("No War")
			return
		}
	}
	fmt.Println("War")
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int MAX_N = 200005;
const int INF = (1e9)+5;
bool visited[MAX_N];
vector<int> G[MAX_N];
int a[MAX_N],dp[MAX_N],ans[MAX_N];
int N;

void init()
{
	rep(i,MAX_N)
	{
		dp[i] = INF;
	}
}

void dfs(int x)
{
	if (visited[x]) return;
	visited[x] = true;
	auto it = lower_bound(dp, dp+N, a[x]);
	int idx = it - dp;
	int v = *it;
	*it = a[x];
	ans[x] = lower_bound(dp, dp+N, INF) - dp;
	rep(i,G[x].size())
	{
		dfs(G[x][i]);
	}
	dp[idx] = v;
	return;
}

int main()
{
	init();
	cin >> N;
	rep(i,N)
	{
		cin >> a[i];
	}
	rep(i,N-1)
	{
		int u,v;
		cin >> u >> v;
		u--;
		v--;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	vector<int> dp;
	dp.push_back(a[0]);
	dfs(0);
	rep(i,N)
	{
		cout << ans[i] << endl;
	}
	return 0;
}

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] line = br.readLine().split(" ");
        boolean[] schedule = new boolean[1000]; // default false

        int a = Integer.parseInt(line[0]);
        int b = Integer.parseInt(line[1]);
        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            line = br.readLine().split(" ");
            int s = Integer.parseInt(line[0]);
            int e = Integer.parseInt(line[1]);
            for (int j = s; j < e; j++) {
                schedule[j] = true;
            }
        }

        boolean result = true;
        for (int i = a; i < b; i++) {
            if (schedule[i]) {
                result = false;
                break;
            }
        }

        if (result) {
            System.out.println("0");
        } else {
            System.out.println("1");
        }
    }
}


Measured memory_bytes: 24496
/******************************************
* AUTHOR : RAJAGOPALAN *
* NICK : ARNO *
* INSTITUTION : VIT *
******************************************/
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define alli(a, n, k) (a+k),(a+n+k)
#define FP(i, a, b, k) for(__typeof(a) i = a;i < b;i += k)
#define FS(i, a, b, k) for(__typeof(a) i = a;i > b;i -= k)
#define IT(it, a) for(__typeof(a.begin()) it = a.begin();it != a.end(); ++it)
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define eps 1e-6
#define pi 3.141592653589793
using namespace std;
using namespace __gnu_pbds;

template<class T> inline T gcd(T x, T y) { if (!y) return x; return gcd(y, x%y);}
typedef vector<int> VII;
typedef vector<ll> VLL;
typedef pair<int, int> PII;
typedef vector< pair<int, int> > VPII;
typedef vector< pair<int, PII > > VPPI;
const int MOD = 1e9 + 7;
const int INF = 1e9;

inline ll modulo(ll a, ll m)
{
    return (a % m + m) % m;
}

inline ll modInverse(ll a, ll m)
{
    assert(__gcd(a, m) == 1);
    ll m0 = m;
    ll y = 0, x = 1;

    if (m == 1)
        return 0;

    while (a > 1)
    {
        ll q = a / m;
        ll t = m;

        m = a % m, a = t;
        t = y;

        y = x - q * y;
        x = t;
    }

    if (x < 0)
        x += m0;

    return x;
}

inline ll modPow(ll x, ll y, ll m)
{ //x^y % m
    if (y == 0)
        return 1LL;
    else if (y == 1)
        return x;
    else
    {
        ll ans = modPow(x, y / 2, m) % m;
        if (y & 1)
        {
            return (((ans * ans) % m) * x) % m;
        }
        else
        {
            return (ans * ans) % m;
        }
    }
}

int main(int argc, char* argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    VPII arr;
    for(int i=1;i<=n;++i)
    {
        int x;
        cin>>x;
        arr.pb({x,i});
    }
    sort(all(arr),less<PII>());
    for(auto xx:arr)
    cout<<xx.second<<' ';
    return 0;
}

Measured memory_bytes: 1780
#include <algorithm>
#include <iostream>

using namespace std;
     
int main(void){
  int N;

  cin >> N;

  int D[N];

  for (int i; i<N; i++) {
    cin >> D[i];
 }

  int jk = 0;

  sort(D, D + N);

  int hanbun = (N-1)/2;

  //cout << hanbun << "\n";

  int hmin = D[hanbun];
  int hmax = D[hanbun+1];

  //cout << hmax << " " << hmin << "\n";

  cout << hmax - hmin;

  return 0;
}

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

l=[0 for i in range(N)]

#Aの数をlで表現
for i in range(N):
  l[A[i]-1] += 1
#lを昇順にソート
l=sorted(l)

ans=0
#なって欲しい数になっていない数の種類はN-K
#それらの玉の数を足す
for i in range(N-K):
  ans += l[i]
print(ans)

Measured memory_bytes: 32244
#include <bits/stdc++.h>
#define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
using namespace std;
typedef long long ll;

string S, T;

int main(void) {
  cin >> S >> T;

  vector<string> ans;
  REP(i, 0, S.length() - T.length() + 1) {
    bool f = true;
    REP(j, 0, T.length()) f = f && (S[i + j] == T[j] || S[i + j] == '?');
    if(f) {
      string s = S;
      REP(j, 0, T.length()) s[i + j] = T[j];
      REP(j, 0, s.length()) if(s[j] == '?') s[j] = 'a';
      ans.push_back(s);
    }
  }

  sort(ans.begin(), ans.end());
  if(ans.size() > 0) cout << ans[0] << endl;
  else cout << "UNRESTORABLE" << endl;
}


Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,n) for(int i=(a); i<(n); i++)
#define ALL(v) v.begin(), v.end()
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

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

	map<char, int> cnt;
	rep(i, w.size()) {
		if (cnt.count(w[i])) ++cnt[w[i]];
		else cnt[w[i]] = 1;
	}

	bool flag = true;
	for(auto c: cnt) {
		auto value = c.second;
		// cout << key << " " << value << endl;
		if (value%2==1) flag = false;
	}

	if (flag) puts("Yes");
	else puts("No");
}

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

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; }

using ll = long long;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int INF = 1<<30;
const ll mod = 1000000007LL;

int main() {
  int N;
  cin>>N;
  vector<vector<int>> graph(N);
  for(int i = 0; i < N-1; i++){
    int x,y;
    cin>>x>>y;
    graph[x-1].push_back(y-1);
    graph[y-1].push_back(x-1);
  }
  queue<int> bfs;
  vector<int> col(N,0);
  vector<bool> seen(N,false);
  bfs.push(0);
  col[0]=0;
  seen[0]=true;
  vector<int> cnt(2,0);
  cnt[0]++;
  while(!bfs.empty()){
    int t = bfs.front();
    bfs.pop();
    for(auto nx:graph[t]){
      if(seen[nx]) continue;
      seen[nx]=true;
      col.at(nx)=1-col.at(t);
      bfs.push(nx);
      cnt.at(col.at(nx))++;
    }
  }
  queue<int> a,b,c;
  for(int  i = 1; i <=N; i++){
    if(i%3==1)a.push(i);
    if(i%3==2)b.push(i);
    if(i%3==0)c.push(i);
  }
  vector<int> ans(N,0);
  if(cnt.at(0)<=(int)c.size()){
    for(int i = 0; i < N; i++){
      if(col.at(i)==0){
        ans.at(i)=c.front();
        c.pop();
      }
      if(col.at(i)==1){
        if(!b.empty()){
          ans.at(i)=b.front();
          b.pop();
        }
        else if(!a.empty()){
          ans.at(i)=a.front();
          a.pop();
        }
        else if(!c.empty()){
          ans.at(i)=c.front();
          c.pop();
        }
      }
    }
  }
  else if(cnt[1]<=(int)c.size()){
    for(int i = 0; i < N; i++){
      if(col.at(i)==1){
        ans.at(i)=c.front();
        c.pop();
      }
      if(col.at(i)==0){
        if(!b.empty()){
          ans.at(i)=b.front();
          b.pop();
        }
        else if(!a.empty()){
          ans.at(i)=a.front();
          a.pop();
        }
        else if(!c.empty()){
          ans.at(i)=c.front();
          c.pop();
        }
      }
    }
  }
  else {
    for(int i = 0; i < N; i++){
      if(col.at(i)==0){
        if(!a.empty()){
          ans.at(i)=a.front();
          a.pop();
        }
        else if(!c.empty()){
          ans.at(i)=c.front();
          c.pop();
        }
      }
      if(col.at(i)==1){
        if(!b.empty()){
          ans.at(i)=b.front();
          b.pop();
        }
        else if(!c.empty()){
          ans.at(i)=c.front();
          c.pop();
        }
      }
    }
  }
  for(auto x: ans) cout<<x<<" ";
  cout<<endl;
}

Measured memory_bytes: 15476
#include<bits/stdc++.h>
#define ll long long
#define uint unsigned
#define ull unsigned ll
#define pii pair<int,int>
#define pll pair<ll,ll>
#define PB push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define CLR(a,v) memset(a,v,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(a))
using namespace std;
int m,d,ans;
int main(){
	scanf("%d%d",&m,&d);
	For(i,1,d){
		int v1=i%10,v2=i/10;
		if (v1*v2>0&&v1*v2<=m&&v1>=2&&v2>=2) ++ans;
	}
	printf("%d\n",ans);
} 

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

int main(){
	int field[51][51] = {},dp[51][51] = {};
	int h,w;
	string s;
	cin >> h >> w;
	for(int i = 1;i <= h;i++){
		cin >> s;
		for(int j = 0;j < w;j++){
			field[i][j + 1] = s[j] - '0';
		}
	}
	for(int i = 1;i <= h;i++){
		for(int j = 1;j <= w;j++){
			if(i >= 2 && j >= 2) dp[i][j] = min(dp[i - 1][j],dp[i][j - 1]) + field[i][j];
			else if(i >= 2) dp[i][j] = dp[i - 1][j] + field[i][j];
			else if(j >= 2) dp[i][j] = dp[i][j - 1] + field[i][j];
		}
	}
	cout << dp[h][w] << endl;
	return 0;
}

Measured memory_bytes: 3236
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    x, k, d = map(int, input().split())
    cycle = abs(x) // d     # cycle:距離ｘを距離ｄ移動で詰めるための必要移動回数。
    if cycle >= k:          # xまでの移動でｋが尽きる場合。
        print(abs(abs(x) - k * d))
    else:                   # xまで移動してｋが余る場合。
        k -= cycle          # ｋ＝余る移動回数、にする
        if k&1:             # kが奇数なら「ｘを飛び越えた地点」に留まるのが最適解。
            print(abs(abs(x) - (cycle + 1) * d))
        else:
            print(abs(abs(x) - (cycle) * d))

if __name__ == '__main__':
    main()

Measured memory_bytes: 61848
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        String str = scan.next();
        String[] strArray = new String[str.length()];
        String r = "R";
        int redcount = 0;
        int bulecount = 0;

        for (int i = 0; i < str.length(); i++) {
            String str2 = String.valueOf(str.charAt(i));
            strArray[i] = str2;

            if(strArray[i].equals(r)){
                redcount++;
            }
            
            else{
                bulecount++;
            }

        }

        if((redcount - bulecount) > 0){            
            System.out.println("Yes");
        }
        else{
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 22996
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Object o = run();
        if (o != null)
            System.out.println(o);
    }

    static Object run() {
        try (Scanner sc = new Scanner(System.in)) {
            int n = sc.nextInt();
            int x = sc.nextInt();
            int t = sc.nextInt();
            int a = 0;
            a = (n % x != 0) ? 1 : 0;
            return (n / x + a) * t;
        }
    }
}

class ChenNumberUtil {
    static Collection<Integer> getDivisors(int n) {
        ArrayList<Integer> al = new ArrayList<>();
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                al.add(i);
                if (n / i != i)
                    al.add(n / i);
            }
        }
        Collections.sort(al);
        return al;
    }
}

class ChenBitUtil {
    static int popCount(int bit) {
        return Integer.bitCount(bit);
    }

    static boolean isFlag(int bit, int i) {
        return 0 != (bit & (1 << i));
    }

    static int setTrue(int bit, int i) {
        return bit |= (1 << i);
    }

    static int setFalse(int bit, int i) {
        return bit &= ~(1 << i);
    }

    static int setReverse(int bit, int i) {
        return isFlag(bit, i) ? setFalse(bit, i) : setTrue(bit, i);
    }

    static int reverseAll(int bit) {
        return ~bit;
    }
}


Measured memory_bytes: 27048
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;

const int MAX_H = 10101;

bool ng[MAX_H][4];
ll dp[MAX_H][1 << 4];

bool check(int y, int bit) {
    for (int x = 0; x < 4; x++) {
        if (ng[y][x] && !(bit >> x & 1)) return false; 
    }
    return true;
}

int main() {
    int h, n;
    cin >> h >> n;
    for (int i = 0, x, y; i < n; i++) {
        cin >> x >> y;
        ng[y][x] = true;
    }

    for (int i = 0; i < h - 1; i++) {
        for (int bit = 0; bit < 1 << 4; bit++) {
            if (!check(i, bit)) continue;
            for (int bit2 = 0; bit2 < 1 << 4; bit2++) {
                if (!check(i + 1, bit2)) continue;
                for (int j = 0; j < 3; j++) {
                    if (bit >> j & 1) continue;
                    if (bit >> (j + 1) & 1) continue;
                    if (bit2 >> j & 1) continue;
                    if (bit2 >> (j + 1) & 1) continue;
                    int t = bit2 | (1 << j) | (1 << (j + 1));
                    dp[i + 1][t] = max(dp[i + 1][t], dp[i][bit] + 1);
                }
                if (bit == 0 && bit2 == 0) {
                    dp[i + 1][(1 << 4) - 1] = max(dp[i + 1][(1 << 4) - 1], dp[i][0] + 2);
                }
                dp[i + 1][bit2] = max(dp[i + 1][bit2], dp[i][bit]);
            }
        }
    }
    ll ans = 0;
    for (int bit = 0; bit < 1 << 4; bit++) {
        ans = max(ans, dp[h - 1][bit]);
    }
    cout << ans << endl;
}


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

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

    int ans = 0, count = 0;
    for(int i = 0; i < N - 1; i++){
        if(H[i] < H[i + 1]){
            ans = max(ans, count);
            count = 0;
        }else{
            count++;
        }
    }
    ans = max(ans, count);

    cout << ans << endl; 
}

Measured memory_bytes: 640
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>; 
using pll = pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1001001001LL;
constexpr long long LINF = 1001001001001001001;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define rept(i, j, n) for(int i=(j); i<(n); i++)
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; }


int main(){
    int n, m; cin >> n >> m;
    vector<pii> A(n);
    rep(i, n){
        int a, b; cin >> a >> b;
        a = m - a; //a日目までに請けないといけない
        A[i] = {a, b};
    }
    sort(all(A), greater<pii>());
    ll res = 0; int index = 0;
    priority_queue<int> que;
    for(int i=m; i>=0; i--){
        while(index < n){
            if(A[index].first != i)break;
            que.push(A[index].second);
            index++;
        }
        if(que.size()){
            int point = que.top(); que.pop();
            res += point;
        }
    }
    cout << res << ln;
}
    


Measured memory_bytes: 4632
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define repr(e,x) for(auto& e:x)
using namespace std;
typedef long long ll;

ll N;
ll A[100000], B[100000], C[100000];

int main(){
    cin>>N;
    rep(i,N) cin>>A[i];
    rep(i,N) cin>>B[i];
    rep(i,N) cin>>C[i];
    sort(A,A+N);
    sort(B,B+N);
    sort(C,C+N);

    ll ans=0;
    ll ai=0, ci=0;
    rep(i,N){
        ll a,c;
        while(A[ai]<B[i] && ai<N) ai++;
        a=ai;

        while(!(B[i]<C[ci]) && ci<N) ci++;
        c=N-ci;

        ans+=a*c;
    }
    
    cout<<ans<<endl;
}

Measured memory_bytes: 2560
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<list>
#include<set>
#include<cstring>
#include<string>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    int t=0,x=0,y=0,a,b,c;
    for(int i=1;i<=n;i++){
        scanf("%d %d %d",&c,&a,&b);
        if(abs(x-a)+abs(y-b)>c-t){
            printf("No\n");
            return 0;
        }
        if((abs(x-a)+abs(y-b))%2!=(c-t)%2){
            printf("No\n");
            return 0;
        }
        x=a;y=b;t=c;
    }
    printf("Yes\n");
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
typedef long long ll;

int main(){
    ll  n;
    ll  a[86+1] = {2,1};
    scanf("%lld", &n);

    for(int i=2; i<=n; i++){ a[i] = a[i-2] + a[i-1]; }

    printf("%lld\n", a[n]);
    return 0;
}

Measured memory_bytes: 1724
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

int main(void){
	int n,l;
	cin >> n >> l;
	vector<string> v;
	for(int i=0;i<n;i++) {
		string s;
		cin >> s;
		v.push_back(s);
	}
	sort(v.begin(),v.end());
	for(auto i:v) cout << i;
	cout << endl;
}

Measured memory_bytes: 256
# D - Equals Union Find

N, M = map(int, input().split())
p = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(M)]

# 負ならそのノードが根かつ絶対値が木の要素数を示す、正なら値のノードが根であることを示す
root = [-1] * N 

# 木の高さを示す
rank = [1] * N

# インデックスxを与えると、xの根を返す関数
def find_root(x):
    if root[x] < 0:
        return x
    else:
        root[x] = find_root(root[x])
        return root[x]
    
# インデックスx,yを与えると、xとyの木を統合する関数
def union(x,y):
    # root_x, root_yは根のインデックス
    root_x = find_root(x)
    root_y = find_root(y)
    if root_x == root_y:
        return
    elif rank[root_x] > rank[root_y]: # 短い木(yの方)を長い木(xの方)に繋ぐ
        root[root_x] += root[root_y] # 要素数結合
        root[root_y] = root_x # 根を切り替え
    else:
        root[root_y] += root[root_x]
        root[root_x] = root_y
        
        if rank[root_x] == rank[root_y]:
            rank[root_y] += 1 # 新しい木の高さを1追加
            
for idx in range(M):
    union(xy[idx][0]-1, xy[idx][1]-1)
    
ans = 0
for i in range(N):
    if find_root(i) == find_root(p[i]-1):
        ans += 1
        
print(ans)

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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define REP(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define each(i,c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define all(v) v.begin(), v.end()
#define mset(a, n) memset(a, n, sizeof(a))

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

const int INF = 1000000000;
const int MOD = 1000000007;
const double eps = 1e-9;

int main(int argc, char *argv[]) {
    // cin.tie(0);
    // ios::sync_with_stdio(false);
    int a, b, c;
    cin >> a >> b >> c;
    if (c >= a && c <= b) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

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

   int A[N+5];

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

   bool judge;
   judge=true;
   int ans=0;

   while(judge){
       for(int i=0;i<N;i++){
           if(A[i]%2==0){
               A[i] = A[i] / 2;
           }
           else{
               judge=false;
               break;
           }
        }
        if(judge){
            ans++;
        }
   }
   cout << ans << endl;
   return 0;
}

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

using namespace std;
template<typename T>
using reversed_priority_queue = std::priority_queue<T, std::vector<T>, std::greater<T> >;
typedef unsigned long long int ull;
typedef long long int ll;
#define rep(i,a,b) for (ll i=(a); i<(b); i++)
typedef pair<ll,ll> PLL;
// }}}

signed main() {
    ll n,m;
    cin>>n>>m;
    vector<set<ll>> edge(n, set<ll>());
    rep(i,0,m){
        ll a,b;
        cin>>a>>b;
        a--; b--;
        edge[a].insert(b);
        edge[b].insert(a);
    }

    bool ok = false;
    rep(i,1,n-1){
        auto c1 = edge[0].count(i);
        auto c2 = edge[n-1].count(i);
        if (c1 > 0 && c2 > 0){
            ok =true;
            break;
        }
    }
    cout<<(ok?"POSSIBLE":"IMPOSSIBLE")<<endl;
    return 0;
}


Measured memory_bytes: 28416
fun main(args : Array<String>) {
    val (N, M) = readLine()!!.split(" ").map { it.toLong() }
    val fact = primeFactor(M.toInt())
    val MOD = 1000000000+7L
    var ans = 1L
    fact.entries.forEach {
        // N 個
        ans = ans * nCk(it.value + (N-1), N-1, MOD) % MOD
    }
    println(ans)
}


// O(N^0.5)
// O(√n)
fun primeFactor(n: Int) : Map<Int, Int> {
    val map = mutableMapOf<Int, Int>()
    var num = n;
    for (i in 2..(Math.sqrt(n.toDouble())).toInt()) {
        // iで割れるところまで割り続ける
        while (num % i == 0) {
            if (map[i] == null) {
                map[i] = 1
            } else {
                map[i] = 1 + map[i]!!
            }
            num /= i;
        }
    }
    // 残りが1じゃなかったらそれもカウントする
    if (num != 1) map[num] = 1

    return map
}
/*
fun primeFactor(N: Long) : Map<Long, Long> {
    val map = hashMapOf<Long, Long>();
    var num = N
    (2..(Math.sqrt(N.toDouble()).toLong())).forEach {
        var count = 0L
        while (num % it == 0L) {
            num /= it
            count++
        }
        map[it] = count
    }

    if (num != 1L) {
        map[num] = 1
    }

    return map
}
*/

fun pow(a: Long, b: Long, M: Long): Long {
    var b = b
    var ret: Long = 1
    var tmp = a
    while (b > 0) {
        if (b and 1 == 1L) ret = ret * tmp % M
        tmp = tmp * tmp % M
        b = b shr 1
    }
    return ret
}
fun nCk(n: Long, k: Long, M: Long): Long {
    var ret: Long = 1
    val min = Math.min(k, n - k)
    for (i in 1..min) {
        ret = ret * pow(i, (M - 2), M) % M
    }
    for (i in n - min + 1..n) {
        ret = ret * i % M
    }
    return ret
}

Measured memory_bytes: 38060
#include<bits/stdc++.h>
#define ll long long
#define dbg1(x) cerr<<#x<<"="<<(x)<<" "
#define dbg2(x) cerr<<#x<<"="<<(x)<<"\n"
#define dbg3(x) cerr<<#x<<"\n"
using namespace std;
#define reg register
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
const int MN=51;
ll N,X,D,v[MN],p[MN],z[MN],id[MN],nm[MN];
vector<int>s[MN];
void dfs(int x)
{
	reg int i;p[x]=1;
	for(i=s[x].size()-1;~i;--i)
		dfs(s[x][i]),v[x]+=v[s[x][i]],p[x]+=p[s[x][i]];
}
ll f[MN*MN*MN];
bool cmp(const int&x,const int&y){return p[x]*v[y]>p[y]*v[x];}
signed main()
{
	N=read(),X=read(),D=read();
	reg ll i,j,k;ll lim=0;
	for(v[1]=read(),i=2;i<=N;++i)
		v[i]=read(),s[read()].push_back(i),z[i]=min(D,N);
	dfs(1);z[1]=N;
	for(i=1;i<=N;++i)lim+=z[i]*p[i];
	for(i=1;i<=lim+1;++i)f[i]=1e18;
	for(i=1;i<=N;++i)for(j=lim;j;--j)
	{
		ll r=min(z[i],j/p[i]);
		for(k=1;k<=r;++k)f[j]=min(f[j],f[j-p[i]*k]+v[i]*k);
		f[j]=min(f[j],f[j+1]);
	}
	for(z[1]=1e18,i=2;i<=N;++i)z[i]=D-z[i];
	for(i=1;i<=N;++i)id[i]=i;
	std::sort(id+1,id+N+1,cmp);
	ll ans=0;
	for(j=X,i=1;i<=N;++i)
	{
		nm[i]=min(z[id[i]],j/v[id[i]]);
		ans+=p[id[i]]*nm[i];
		j-=v[id[i]]*nm[i];
	}
	ll tmp=ans;
	for(j=X-j,k=i,i=1;i<=lim;++i)
	{
		if(f[i]>X)break;
		ll most=X-f[i];
		while(j>most)
		{
			while(!nm[k])--k;
			ll n=(j-most+v[id[k]]-1)/v[id[k]];
			n=min((ll)n,nm[k]);nm[k]-=n;
			j-=v[id[k]]*n;tmp-=p[id[k]]*n;
		}
		ans=max(ans,tmp+i);
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 768
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
#define rep(i,n) for (int i=0;i<N;i++)

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

  int retval = 0;
  while (S.size()>0) {
    S.erase(S.size()-2);
    if (S.substr(S.size()/2) == S.substr(0,S.size()/2)){
      retval = S.size();
      break;
    }

        
  }

  cout << retval << endl;

}

 

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	@SuppressWarnings("resource")
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String scan="";
		while(sc.hasNext()) scan += sc.nextLine();
		scan = scan.toLowerCase();
		char abc[] = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
		int count[] = new int[abc.length];

		for(int i=0;i<scan.length();i++) {
			for(int j=0;j<abc.length;j++) {
				if(scan.charAt(i)==abc[j]) count[j]++;
			}
		}
		for(int i=0;i<abc.length;i++) {
			System.out.println(abc[i]+" : "+count[i]);
		}
	}

}



Measured memory_bytes: 26140
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <numeric>
#include <bitset>
#include <math.h>
#include <iomanip>
#include <sstream>

using namespace std;
typedef long long ll;

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
#define PI 3.14159265359 //πの値
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素
#define C(x) cout << x << endl //テスト出力

//関数
//nCkの計算の関数(呼び出しは[cbn])
ll cbn(ll n, ll k) {
    ll r = 1;
    for (ll d = 1; d <= k; ++d) {
        r *= n--;
        r /= d;
    }
    return r;
}
// a^n mod を計算する
ll powmod(ll a, ll n) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}
//２つの最大公約数
int gcb(int a, int b){
    if(a < b){
        int x = a;
        a = b;
        b = x;
    }
    int amari = a % b;
    if(amari == 0) return b;

    return gcb(b, amari);
}
//３つの最大公約数
int gcb_3(int a, int b, int c){
    return gcb(gcb(a, b), c);
}

/*map<Keyの型, Valueの型> 変数名;
queue<型> 変数名;
priority_queue<型> 変数名;
priority_queue<型, vector<型>, greater<型>> 変数名;
vector<vector<要素の型>> 変数名(要素数1, vector<要素の型>(要素数2, 初期値))*/

/*-----------------------------ここから-----------------------------*/

int main() {
cin.tie(0);
ios::sync_with_stdio(false);
ll n; cin>>n;
vector<ll> data(n);
REP(i,n) cin>>data[i];
ll cnt = 0;
for(ll i = 0; i<n;i++) for(ll j=i+1;j<n;j++) cnt+=data[i]*data[j];
cout<<cnt;
}

Measured memory_bytes: 3636
k=gets.to_i
z=*1..9
a=0
k.times{
  a=z.shift
  b=a%10
  z << a*10 + (b-1) if b != 0
  z << a*10 + b
  z << a*10 + (b+1) if b != 9
  }
p a

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

int main(void){
  int dp[1001], n, m;
  while(cin >> n >> m && n && m){
    memset(dp, 0, sizeof(dp));
    dp[1] = 0;
    for(int i = 2; i <= n; i++){
      dp[i] = (dp[i-1] + m) % i;
    }
    cout << dp[n] + 1 << endl;
  }
  return 0;
}

Measured memory_bytes: 1164
#include<iostream>
using namespace std;
int main()
{
    int n;
	long long a[86]={2,1};
	cin>>n;
	for(int i=2;i<=n;i++)
		a[i]=a[i-1]+a[i-2];
	cout<<a[n]<<endl;
    return 0;
}

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

int main(){
    int n; cin >> n;
    vector<int> a(n), b(n, 0); int64_t ans = 0;
    for (auto i = 0; i < n; i++) cin >> a[i], ans += a[i];
    for (auto i = 1; i < n; i += 2) ans -= 2 * a[i];
    cout << ans << " ";
    for (auto i = 1; i < n; i++) ans = 2 * a[i - 1] - ans, cout << ans << " ";
    cout << endl;
    return 0;
}

Measured memory_bytes: 3936
#include <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#include <utility>
#define llint long long
#define inf 1e18
#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)
#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))

using namespace std;
typedef pair<llint, llint> P;

llint k;
vector<llint> vec;
llint mul = 0;

void dfs(int n, int d)
{
	if(n == 10){
		if(mul != 0) vec.push_back(mul);
		return;
	}
	if(d == -1){
		dfs(n+1, -1);
		for(int i = 1; i <= 9; i++){
			if(n == 0 && i >= 4) break;
			mul *= 10, mul += i;
			dfs(n+1, i);
			mul /= 10;
		}
	}
	else{
		for(int i = -1; i <= 1; i++){
			int c = d + i;
			if(c < 0 || c > 9) continue;
			mul *= 10, mul += c;
			dfs(n+1, c);
			mul /= 10;
		}
	}
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> k;
	dfs(0, -1);
	sort(vec.begin(), vec.end());
	//for(int i = 0; i < 30; i++) cout << vec[i] << " "; cout << endl;
	cout << vec[k-1] << endl;
	
	return 0;
}

Measured memory_bytes: 1400
#define ll				long long
#define MOD				1000000007
#define VTX_MAX			10000
#define EDGE_MAX		10000

#include <float.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>


FILE *in, *ans;
int tno;

int out(const char *s) {
#ifdef TEST
	char buf[8192];
	fgets(buf, sizeof(buf), ans);
	if (strcmp(buf, s)) {
		printf("err\n");
	}
#else
	printf(s);
#endif
	return 0;
}

int outi(int i) {
	char s[128];
	sprintf(s, "%d\n", i);
	out(s);
	return 0;
}

int outd(double d) {
	char s[128];
	sprintf(s, "%.10lf\n", d);
	out(s);
	return 0;
}

int outll(ll l) {
	char s[128];
	sprintf(s, "%lld\n", l);
	out(s);
	return 0;
}

int geti() {
	int i;
	fscanf(in, "%d", &i);
	return i;
}

ll getll() {
	ll l;
	fscanf(in, "%lld", &l);
	return l;
}

int getstr(char *s) {
	fscanf(in, "%s", s);
	return 0;
}

int n, a, b, c, d;
char s[200010];

int move(int f, int t) {
	int i;


	for (i = f; i < t; i++) {
		if (s[i + 1] == '#') {
			if (s[i + 2] == '#') {
				return -1;
			}
			i++;
		}
	}

	return 0;
}

int moveb() {
	while (b < d) {
		b++;
		if (s[b] == '.') {
			return 0;
		}
	}

	return -1;
}

int move2() {
	int ret;

	for ( ; a < c; a++) {
		if (s[a + 1] == '#' || a + 1 == b) {
			if (s[a + 2] == '#' || a + 2 == b) {
				if (a + 1 == b) {
					ret = moveb();
					if (ret != 0) {
						return -1;
					}
				}
				else if (a + 2 == b) {
					ret = moveb();
					if (ret != 0) {
						return -1;
					}
					a++;
				}
				else {
					return -1;
				}
			}
			else {
				a++;
			}
		}
	}

	return 0;
}

int fnc2() {
	int i, j, k, ret;

	n = geti();
	a = geti() - 1;
	b = geti() - 1;
	c = geti() - 1;
	d = geti() - 1;
	getstr(s);

	ret = move(b, d);
	if (ret != 0) {
		return -1;
	}

	if (c < d) {
		ret = move(a, c);
	}
	else {
		ret = move2();
	}
	if (ret != 0) {
		return -1;
	}

	return 0;
}

int fnc1() {
	int ret = fnc2();
	if (ret == 0) {
		out("Yes\n");
	}
	else {
		out("No\n");
	}
	return 0;
}

int main() {

#ifdef TEST
	for (tno = TEST_SNO; tno <= TEST_ENO; tno++) {
		char str[128];
		sprintf(str, "test%d.txt", tno);
		in = fopen(str, "r");
		sprintf(str, "ans%d.txt", tno);
		ans = fopen(str, "r");
		fnc1();
		fclose(in);
		fclose(ans);
	}
	printf("end\n");
#else
	in = stdin;
	fnc1();
#endif

	return 0;
}


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

    int n,l;
    vector<int> a,b,c,u,p;
    vector<vector<int>> d;

void dp(int s,int ans){
    if (p.at(s)==1) return ;
    u.at(s)=ans;
    p.at(s)=1; 
    for (int i=0;i<d.at(s).size();i++){
        if (a.at(d.at(s).at(i))==s) l=b.at(d.at(s).at(i));
        if (b.at(d.at(s).at(i))==s) l=a.at(d.at(s).at(i));
        
        if (c.at(d.at(s).at(i))%2==0) dp(l,ans);
        else {
            dp(l,1 - ans);
        }
    }
    return ;
}

int main(void){
    // Your code here!
    cin >> n;
    a.resize(n);b.resize(n);c.resize(n);u.resize(n+1);p.resize(n+1);
    d.resize(n+1,vector<int>(0));
    
    for (int i=1;i<n;i++){
        cin >> a.at(i) >> b.at(i) >> c.at(i);
        d.at(a.at(i)).push_back(i);
        d.at(b.at(i)).push_back(i);
    }
    dp(1,0);
    for (int i=1;i<n+1;i++){
        cout << u.at(i) << endl;
    }
}

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

#define f first
#define s second
#define pb push_back

#define ll long long

#define mp make_pair

#define int ll

using namespace std;
                        

const int inf = 1e9 + 7;

const ll ll_inf = 1e18 + 7;
const int K = 18;
const int N = 5e5 + 100;
                        

ll binpow (ll a, ll n)
{
    ll res = 1;
    while (n) {
        if (n & 1)
        {
            res *= a;
            res %= inf;
        }
        a *= a;
        n >>= 1;
        a %= inf;
    }                      	
    return res;
}   

void boost()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
          
string s;

main()
{
	cin >> s;
	if (s.size() != 6)
	{
		cout << "No";
		return 0;
	}
	if (s[2] == s[3] && s[4] == s[5])
	{
		cout << "Yes";
		return 0;
	}
	cout << "No";
}


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

using namespace std;

int main() {
	int A, B;
	cin >> A >> B;

	int Q = A + (A - 1);
	int W = B + (B - 1);
	int E = A + B;

	cout << max({ Q,W,E }) << endl;

	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int i,j,n,f;
    char x[105];
    scanf("%d",&n);
    scanf("%s",x);
    if(n%2!=0)
    {
        printf("No\n");
    }
    else
    {
        f=n/2;
        j=0;
        for(i=0;i<f;i++)
        {
            if(x[i]!=x[i+f])
            {
                j=1;
                break;
            }
        }
        if(j==0)
        {
            printf("Yes\n");
        }
        else
        {
            printf("No\n");
        }
    }
    return 0;
}


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

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

    int ans = 0;
    int tmp = 0;

    for (int i = 0; i < S.length(); i++) {
        if (S[i] == 'A' || S[i] == 'T' || S[i] == 'G' || S[i] == 'C') {
            tmp++;
        } else {
            ans = max(ans, tmp);
            tmp = 0;
        }
    }
  	ans = max(ans, tmp);

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

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <limits>
#include <stack>
#include <math.h>
#define REP(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define RREP(i,n) for(ll i=(n)-1; i>=0; --i)
#define SREP(i,s,n) for(ll i=(s), i##_len=(n); i<i##_len; ++i)


using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

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

bool comp(pair<ll, ll> a, pair<ll, ll> b) {
    return a.second > b.second;
}

struct UnionFind {
    vector<int> par;
    vector<int> rank;
    
    UnionFind(int n = 1) {
        init(n);
    }
    
    void init(int n = 1) {
        par.resize(n); rank.resize(n);
        for (int i = 0; i < n; ++i) {
            par[i] = i;
            rank[i] = 0;
        }
    }
    
    int root(int x) {
        if (par[x] == x) {
            return x;
        }
        else {
            int r = root(par[x]);
            return par[x] = r;
        }
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        return true;
    }
};

#define MOD (1000000007)

void d(vector<vector<pair<ll, ll>>> &EV, vector<ll> &C, ll s, ll N) {
    map<ll, bool> seeked;
    stack<ll> st;
    st.push(s);
    while (st.size()) {
        ll node = st.top();
        st.pop();
        REP(i, EV[node].size()) {
            ll next = EV[node][i].first;
            ll edge_cost = min(EV[node][i].second, C[node]);
            C[next] = max(C[next], edge_cost);
            if (!seeked[next]) st.push(next);
        }
        seeked[node] = true;
    }
}

int main(int argc, const char * argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll N, M;
    cin >> N >> M;
    
    vector<ll> a(M);
    vector<vector<ll>> c(M);
    vector<ll> d(M);
    REP(i, M) {
        cin >> a[i];
        int b;
        cin >> b;
        REP(j, b) {
            int cj;
            cin >> cj;
            c[i].push_back(cj);
            d[i] |= 1 << (cj-1);
        }
    }
    
    vector<ll> dp(4096, 1e17);
    dp[0] = 0;
    REP(i, M) {
        REP(j, 4095) {
            dp[j|d[i]] = min(dp[j|d[i]], dp[j] + a[i]);
        }
    }
    
    if (dp[(1L<<N)-1] == 1e17) {
        cout << -1 << endl;
    }else {
        cout << dp[(1L<<N)-1] << endl;
    }
    
    
}


Measured memory_bytes: 512
/**
 *    author:  erekle
 *    created: 19.09.2020 13:26:02
**/
#include <bits/stdc++.h>

using namespace std;

#define fastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define swap2(x,y) x=x^y; y=x^y; x=x^y;

int main() {
	fastIO
	
	long long n, x, m;
	cin >> n >> x >> m;

	vector<int> order, index(m); // index is one-based
	int repStart = -1; // repeat start value
	for (long long i = x; true; i = (i*i) % m) {
		if (index[i]) {
			repStart = i;
			break;
		}
		order.push_back(i);
		index[i] = order.size();
	}

	long long ans = 0;
	for (int i = 0; i < min(n, (long long)order.size()); ++i) ans += order[i];
	if (n <= order.size()) {
		cout << ans << endl;
		return 0;
	}

	int repLen = (int)order.size() + 1 - index[repStart];
	long long repCount = (n - order.size()) / repLen;
	for (int i = index[repStart] - 1; i < (int)order.size(); ++i) {
		ans += repCount * order[i];
	}
	
	long long pos = (int)order.size() + repCount*repLen + 1;
	for (long long i = repStart; pos <= n; ++pos, i = (i*i) % m) {
		ans += i;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 4016
N = list(input())

nup = sorted(N)

if N[1:len(N)+1] == ["9"] * (len(N)-1):
    sum1 = 0
    for i in range(len(N)):
        sum1 += int(N[i])
    print(sum1)

else:
    print(9*(len(N)-1) + int(N[0])-1)


Measured memory_bytes: 2940
#include <stdio.h>
int main()
{
	int n,a[200],b=0,i,c=0;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(i=0;i<n;i++)
	{
		if(a[i]%2==0)
		b++;
	}
	if(b!=n)
	printf("%d\n",c);
	else
	{
		while(b==n)
		{
			c++;
			b=0;
			for(i=0;i<n;i++)
			{
				a[i]=a[i]/2;
				if(a[i]%2==0)
				b++;
			}
		}
		printf("%d\n",c);
	}
	return 0;
}

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

using namespace std;

int main() {

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

	vector<int> dp(3);

	for(int day = 0; day < n; day++) {
		vector<int> c(3);
		vector<int> new_dp(3, 0);

		for(int i = 0; i<3; i++) scanf("%d", &c[i]);

		for(int i = 0; i<3; i++) {
			for(int j = 0; j<3; j++) {
				if(i != j) 
					new_dp[j] = max(new_dp[j], dp[i] + c[j]);
			}
		}

		dp = new_dp;
	}

	printf("%d", max({dp[0], dp[1], dp[2]}));
}


Measured memory_bytes: 256
N = int(input())
li = [int(input()) for i in range(5)]
ans = 0

if N <= min(li):
  ans = 5
elif N > min(li) and N % min(li) == 0:
  ans = N // min(li) + 4
else:
  ans = N // min(li) + 5
print(ans)

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

int main(){
    int n,q;
    string s;
    cin >> n >> q >> s;
    int l[q],r[q];
    for(int i = 0; i < q; i++){
        cin >> l[i] >> r[i];
    }
    int ac[n] = {};
    for(int i = 1; i < n; i++){
        if(s[i-1] == 'A' && s[i] == 'C'){
            ac[i] += 1;
        }
        ac[i+1] += ac[i];
    }
    for(int i = 0; i < q; i++){
        cout << ac[r[i]-1] - ac[l[i]-1] << endl;
    }
    return 0;
}

Measured memory_bytes: 2176
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define All(a) a.begin(),a.end()
#define INF 1000000007
const int MOD = 1000000007;
//accumulate(vec.begin(), vec.end(), 0)

int gcd(int x,int y){
  if(x%y==0) return y;
  else return gcd(y,x%y);
}

bool isPrime(int n){
  if(n < 2) return false;
  else if(n == 2) return true;
  else if(n%2==0) return false;

  for(int i=3;i<=sqrt(n);i++){
    if(n%i==0) return false;
  }
  return true;
}

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

  for(int i=0;i<s.size();i++){
    int x = s[i] -'A';
    x = (x+n)%26;
    s[i] = 'A'+x;
  }
  cout<< s <<endl;
}


Measured memory_bytes: 256
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) {
        FastScanner scanner = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);
        int N = scanner.nextInt();
        int[] h = new int[N];
        for(int i= 0; i < N; i++) h[i] = scanner.nextInt();
        //Want the solution at N
        //cost at 0 = 0
        //Overlapping subproblem -> recompute :(
        //                          store intermediate answers :)
        int[] dp = new int[N];
        dp[0] = 0;
        dp[1] = Math.abs(h[1]-h[0]);
        for(int i = 2; i < N; i++) {
//            dp[i] = h[i] + Math.min(dp[i-1], dp[i-2]);
            //Cost of hopping from previous??
            dp[i] = Math.min(Math.abs(h[i] - h[i-1]) + dp[i-1], Math.abs(h[i] - h[i-2]) + dp[i-2]);
//            int min = Math.abs(h[i] - h[i-1]) + dp[i-1];
//            min = Math.min(min, Math.abs(h[i]-h[i-2]) + dp[i-2]);
//            dp[i] = min;
        }
        out.println(dp[N-1]);
        out.flush();
    }
    
    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        
        public FastScanner(Reader in) {
            br = new BufferedReader(in);
        }
        
        public FastScanner() {
            this(new InputStreamReader(System.in));
        }
        
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        int nextInt() {
            return Integer.parseInt(next());
        }
        
        long nextLong() {
            return Long.parseLong(next());
        }
        
        double nextDouble() {
            return Double.parseDouble(next());
        }
        
        String readNextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        
        int[] readIntArray(int n) {
            int[] a = new int[n];
            for (int idx = 0; idx < n; idx++) {
                a[idx] = nextInt();
            }
            return a;
        }
    }
}


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

const int mod=1e9+7;
long long int dp[2005];

int main(){
  int s;
  scanf("%d", &s);
  dp[0]=1;
  dp[1]=dp[2]=0;
  for(int a=0;a<=s;a++){
  	for(int b=3;b<=s;b++){
  		if(a+b<=s)(dp[a+b]+=dp[a])%=mod;
  	}
  }
  printf("%lld ", dp[s]);
}


Measured memory_bytes: 3828