akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n;
long long k, a[N], rmq[1 << 20][20], sum = 0;

long long query (int u, int v) {
    int k = log2(v - u + 1);
    return max(rmq[u][k], rmq[v - (1 << k) + 1][k]);
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i], sum += a[i];

    vector <pair <long long, long long> > vec;
    for (int i = 39; i >= 0; i--) {
        int off = 0, on = 0;
        for (int j = 1; j <= n; j++) off += 1 - ((a[j] >> i) & 1), on += ((a[j] >> i) & 1);
        vec.push_back({1LL << i, (1LL << i) * (off - on)});
    }

    sort(vec.begin(), vec.end());
    vector <pair <long long, long long> > vec1, vec2, all1, all2;
    for (int i = 0; i < vec.size() / 2; i++) vec1.push_back(vec[i]);
    for (int i = vec.size() / 2; i < vec.size(); i++) vec2.push_back(vec[i]);
    for (int mask = 0; mask < (1 << (int)vec1.size()); mask++) {
        long long cost = 0, val = 0;
        for (int i = 0; i < vec1.size(); i++) if (mask & (1 << i)) cost += vec1[i].first, val += vec1[i].second;
        all1.push_back({cost, val});
    }

    for (int mask = 0; mask < (1 << (int)vec2.size()); mask++) {
        long long cost = 0, val = 0;
        for (int i = 0; i < vec2.size(); i++) if (mask & (1 << i)) cost += vec2[i].first, val += vec2[i].second;
        all2.push_back({cost, val});
    }

    sort(all1.begin(), all1.end()); sort(all2.begin(), all2.end());
    for (int i = 0; i < all2.size(); i++) rmq[i][0] = all2[i].second;
    for (int k = 1; k < 20; k++) {
        for (int i = 0; i + (1 << k) - 1 < all2.size(); i++) {
            rmq[i][k] = max(rmq[i][k - 1], rmq[i + (1 << (k - 1))][k - 1]);
        }
    }

    long long ans = 0;
    for (int i = 0; i < all1.size(); i++) {
        long long remcost = k - all1[i].first;
        int pos = upper_bound(all2.begin(), all2.end(), make_pair(remcost, (long long)1e18)) - all2.begin(); pos--;
        if (pos < 0) continue;
        ans = max(ans, all1[i].second + query(0, pos));
    }

    cout << ans + sum;
    return 0;
}


Measured memory_bytes: 197732
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main(void) {
    int i, j, checkpoint;
    int N, M;
    long long tmp, min;
    vector<int> ans;
    vector<long long> a, b, c, d;
    // get input ---------------------------------------
    cin >> N >> M;
    for(i = 0; i < N; i++) {
        cin >> tmp;
        a.push_back(tmp);
        cin >> tmp;
        b.push_back(tmp);
    }
    for(i = 0; i < M; i++) {
        cin >> tmp;
        c.push_back(tmp);
        cin >> tmp;
        d.push_back(tmp);
    }
    // search ------------------------------------------
    for(i = 0; i < N; i++) {
        checkpoint = 0;
        min = abs(a[i]-c[0])+abs(b[i]-d[0]);
        for(j = 0; j < M; j++) {
            tmp = abs(a[i]-c[j])+abs(b[i]-d[j]);
            if(tmp < min) {
                checkpoint = j;
                min = tmp;
            }
        }
        ans.push_back(checkpoint + 1);
    }
    // disp answer ------------------------------------
    for(i = 0; i < ans.size(); i++) {
        cout << ans[i] << endl;
    }
    return 0;
}






Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, j) for(int i = 0; i < (int)(j); i++)
constexpr int INF = 1 << 28;
struct Edge{
    int to;
    ll cost;
    Edge(int to, ll cost):to(to), cost(cost){}
};
using EdgeList = vector<vector<Edge>>;
using Vatex = int;
constexpr ll INFL = 1LL << 60;
struct State{
    int index;
    ll cost;
    State(int i, ll c):index(i), cost(c) {}
    bool operator > (const State &r) const { return cost > r.cost; }
};
//
//
vector<ll> dijkstra(const EdgeList &G, int start) {
    priority_queue<State, vector<State>, greater<State>> que;
    vector<ll> dist(G.size(), INFL);
    que.emplace(start, 0);
    dist[start] = 0;
    while(not que.empty()){
        State now = que.top(); que.pop();
        for(Edge e : G[now.index]){
            if(dist[e.to] > now.cost + e.cost){
                State nxt = State(e.to, now.cost + e.cost);
                dist[e.to] = nxt.cost;                
                que.push(nxt);
            }
        }
    }
    return dist;
}
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp
int main() {
    int N, M, R; cin >> N >> M >> R;
    EdgeList E(N);
    rep(i, M) {
        int a, b, c; cin >> a >> b >> c;
        E[a].push_back(Edge(b, c));
    }
    auto dist = dijkstra(E, R);
    for(ll d : dist) cout << (d < INFL ? to_string(d) : "INF") << endl;
    return 0;
}

Measured memory_bytes: 19368
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const long long INF = 1LL << 60;


int main() {
// 　柱の数 int
long long n;
cin >> n;
// 柱の長さ array
int arr[n];
for (int i = 0; i < n; i++) {
    cin >> arr[i];
}
// 柱のきたときの運動量を記録 array
// 全てに10002を挿入
long long res[n];
for (int i = 0; i < n; i++) {
    res[i] = INF;
}

// 最初は0, 一回飛んだ場合の運動量を記録しておく。
res[0] = 0;

// 柱の数だけfor を回す
// 1,2 ->2,3の順番で埋めていく
for (int i = 0; i < n; ++i) {
    chmin(res[i+1], res[i] + abs(arr[i] - arr[i + 1]));
    chmin(res[i+2], res[i] + abs(arr[i] - arr[i + 2]));
}
    cout << res[n -1] << endl;
}

Measured memory_bytes: 1408
object Main extends App {
  val inputs: Seq[String] = scala.io.Source.stdin.getLines().toList
  val nums = inputs.head.split(" ").map(_.toInt)

  println(solve(nums(0), nums(1), nums(2)))

  def solve(perTime: Int, bake: Int, time: Int): Int = {
    perTime match {
      case t if t <= 0 => 0
      case _ => {
        val bakedNum = time / perTime
        bake * bakedNum
      }
    }
  }
}

Measured memory_bytes: 25536
#include "bits/stdc++.h"
using namespace std;
using ll = long long; using ull = unsigned long long;
//#define int ll
using vb = vector<bool>; using vvb = vector<vb>;
using vi = vector<int>; using vvi = vector<vi>;
using vl = vector<ll>; using vvl = vector<vl>;
template<class T> using V = vector<T>;
template<class T> using vv = vector<V<T>>;
template<class T> using VV = vector<V<T>>;
#define fi first
#define se second
#define maxs(x,y) (x=max(x,y))
#define mins(x,y) (x=min(x,y))
using pii = pair<int,int>; using pll = pair<ll,ll>;
#define FOR(i,a,b) for(ll i = (a); i < (ll)(b); ++i)
#define REP(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(ll i = (ll)(b)-1;i >= a;--i)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define eb(val) emplace_back(val)
const double PI = acos(-1);
const double EPS = 1e-10;
const ll MOD = 1e9+7;
void cioacc(){//accelerate cin/cout
  cin.tie(0);
  ios::sync_with_stdio(false);
}
signed main(){
  int a[3];
  cin >> a[0] >> a[1] >> a[2];
  if(a[0]==a[1]&&a[1]==a[2]) cout << "Yes" << endl;
  else cout << "No" << endl;
}


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

int main()
{
    char S[2][4];
    for(int i = 0; i < 2; ++i) cin >> S[i];
    for(int i = 0; i < 3; ++i) {
        if(S[0][i] != S[1][2-i]) {
            cout << "NO" << endl; return 0;
        }
    }
    cout << "YES" << endl; 
    return 0;
}

Measured memory_bytes: 256
function main(A,B){
  var result = [];
  Array.prototype.push.call(result,A + B,A - B, A * B);
  console.log(Math.max.call({},...result));  
}

const input = require('fs').readFileSync('/dev/stdin','utf8').split(' ');
const A = Number(input[0]);
const B = Number(input[1]);

main(A,B);

Measured memory_bytes: 7372
/* Author - thiolhub */

#include <bits/stdc++.h>

using namespace std;

#define ll              long long int
#define ld              long double
#define db              double
#define pi              3.1415926535897932384626
#define PI              acos(-1.0)
#define endl            "\n"
#define mod             1000000007
#define mk              make_pair
#define pb              push_back
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define ps(x,y)         fixed<<setprecision(y)<<x
#define w(t)            ll t; cin>>t; while(t--)
#define sc(a)	        scanf("%lld",&a);
#define pr(a)	        printf("%lld\n",a)
#define rep(i,a,n)		for(ll i=a;i<n;i++)
#define m(a)		    memset(a,0,sizeof(a))
#define FastIO          ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0)
#define min3(a,b,c)     min(a,min(b,c))


int main(){ FastIO;

int n,i,s=0;cin>>n;
int b[n-1],a[n];
for(i=0;i<n-1;i++) cin>>b[i];
for(i=0;i<n-1;i++){
	if(i==0){
		a[i]=b[i];
		a[i+1]=b[i];
	}
	else{
		a[i+1]=b[i];
		a[i]=min(a[i],b[i]);
	}
	s+=a[i];
}
s+=a[n-1];
cout<<s;
}

Measured memory_bytes: 3648
N = int(input())

pat = [[0 for _ in range(10)] for _ in range(10)]

for i in range(1, N+1):
    pat[int(str(i)[0])][int(str(i)[-1])] += 1

ans = 0

for i in range(1, 10):
    for j in range(1, 10):
        ans += pat[i][j] * pat[j][i]

print(ans)


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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    unordered_set<string> s;
    cin >> N;
    string str;
    while (N--) {
        cin >> str;
        s.insert(str);
    }
    cout << s.size() << endl;
    return 0;
}

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

class Main {

	void solve() {
		
		int[] a = inintar(3);
		Arrays.sort(a);
		out.println(a[0] + a[1]);
		
	}

	public static Scanner in = new Scanner(System.in);
	public static PrintWriter out = new PrintWriter(System.out);

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

	public int inint() {
		return in.nextInt();
	}

	public long inlong() {
		return in.nextLong();
	}
	
	public String instr() {
		return in.next();
	}

	public char inchar() {
		return in.next().charAt(0);
	}
	
	public int[] inintar(int num) {
		int[] a = new int[num];
		for (int i=0; i<num; i++) {
			a[i] = in.nextInt();
		}
		return a;
	}

	public char[] incharar() {
		return in.next().toCharArray();
	}

}

Measured memory_bytes: 21716
n = int(input())
s = [input() for _ in range(n)]
d = {}
ans = []

for st in s:
    d[st] = d.get(st, 0) + 1

t = max(d.values())
ans_append = ans.append

for x in d:
    if d[x] == t:
        ans_append(x)

ans = sorted(ans)
for x in ans:
    print(x)


Measured memory_bytes: 35216
using System;
using System.Linq;

class prog{
  static void Main(){
    
    string S = Console.ReadLine();
    string T = Console.ReadLine();
    bool flag = false;
    for(int i = 0; i < S.Length; i++){
      S = S.Substring(S.Length - 1) + S.Substring(0, S.Length - 1);
      if(S == T) flag = true;
    }
    Console.WriteLine(flag ? "Yes" : "No");
    
  }
}

Measured memory_bytes: 13140
a = input().split()

n = int(a[0])
k = int(a[1])

ar = [0]*(2*k)
ss = [0]*n

for i in range(0,k*2):
  ar[i] = input().split()
  
for i in range(0,len(ar)):
  if(i%2==0):
    del ar[i][:]

for i in range(0,len(ar)):
  if(len(ar[i]) == 0):
    continue
  else:
    if(len(ar[i]) == 1):
      x = int(ar[i][0]) - 1
      ss[x] += 1 
    else:
      for j in range(0,len(ar[i])):
        x = int(ar[i][j]) - 1
        ss[x] += 1 

print(ss.count(0))

Measured memory_bytes: 68304
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define erep(i,a,n) for(int i = a;i<=n;i++)
typedef long long ll;
#define int long long
#define vint vector<int>
#define vvint vector<vector<int>>
#define vstring vector<string>
#define vdouble vector<double>
#define vll vector<ll>:
#define vbool vector<bool>
#define INF 1101010101010101010
#define MOD 1000000007
#define P = pair<int,int>;
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; }

struct UnionFind{
  // 小さい方を大きいほうにくっつける
  // これのおかげでO(logN)になる
  // 親をたどる際に途中経路に結果を残しておくことで根に直接葉をつなげる
  vector<int> d;
  UnionFind(int n=0):d(n,-1){}
  int find(int x){
    // 根を返すfind関数
    // d[x] < 0 -> xは根
    if(d[x] < 0) return x;
    return d[x] = find(d[x]);
  }
  bool unite(int x,int y){
    x = find(x); y = find(y);
    if(x == y) return false;
    if(d[x] > d[y]) swap(x,y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x,int y){return find(x) == find(y);}
  int size(int x){return -d[find(x)];}
};

signed main(){
  int n,m;
  cin >> n >> m;
  UnionFind tree(n);
  rep(i,0,m){
    int a,b,c;
    cin >> a >> b >> c;
    a--;b--;
    tree.unite(a,b);
  }
  int ans = 0;
  rep(i,0,n){
    if(tree.d[i] < 0) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 1024
def cidx(c):
    return ord(c) - ord('a')

def main():
    s = input()
    t = input()
    si = 1
    ti = 1
    sl = [0] * 26
    tl = [0] * 26
    ans = True
    for i in range(len(s)):
        sidx = 0
        tidx = 0
        sc = cidx(s[i])
        tc = cidx(t[i])

        if sl[sc] != 0:
            sidx = sl[sc]
        else:
            sidx = si
            sl[sc] = si
            si += 1

        if tl[tc] != 0:
            tidx = tl[tc]
        else:
            tidx = ti
            tl[tc] = ti
            ti += 1
        
        if sidx != tidx:
            ans = False
            break
    
    yn = "Yes" if ans else "No"
    print(yn)


            

if __name__ == '__main__':
    main()

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

int edge[51];
vector<int> graph[51];

int ans,n,m;
void dfs(int now){
	edge[now]=0;
	ans++;

	for(int to:graph[now]){
		edge[to]--;
		if(edge[to]==1){
			dfs(to);
		}
	}
	return;
}

int main(){
	ans=0;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int a,b;	cin>>a>>b;
		graph[a].push_back(b);
		graph[b].push_back(a);
		edge[a]++;	edge[b]++;
	}

	for(int i=1;i<=n;i++){
		if(edge[i]==1){
			dfs(i);
		}
	}
	cout<<ans<<endl;

	return 0;
}


Measured memory_bytes: 256
N, M = [int(i) for i in input().split()]
ABS = [[int(i) for i in input().split()] for _ in range(N)]

lim = 0
s = 0
for a, b in sorted(ABS, key=lambda ab: ab[0]):
  if lim + b >= M:
    print(s + (M - lim) * a)
    exit()

  lim += b
  s += a * b


Measured memory_bytes: 23524
#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>
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)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
    rep(i,3){
        string s;cin>>s;
        cout<<s[0];
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <set>
using ll = long long;
using uint = unsigned int;
using graph = std::vector<std::vector<ll>>;
using wGraph = std::vector<std::vector<std::pair<ll,ll>>>;
#define rep(i,n) for (int i=0; i < int(n); i++)

using namespace std;
ll MOD7 = 1000000007;
ll MOD9 = 1000000009;
vector<ll> InputVec(ll N){
    vector<ll> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    return A;
}
void OutputVec(vector<ll> A){
    for (int i = 0; i < A.size(); ++i) {
        cout << A[i] << ",";
    }
    cout << endl;
}
vector<vector<ll>> InputVec2d(ll H,ll W){
    vector<vector<ll>> A(H);
    for (int yi = 0; yi < H; ++yi) {
        A[yi] = vector<ll>(W);
    }
    for (int yi = 0; yi < H; ++yi) {
        for (int xi = 0; xi < W; ++xi) {
            cin >> A[yi][xi];
        }
    }
    return A;
}
vector<vector<char>> InputVec2dStr(ll H,ll W){
    vector<vector<char>> A(H);
    for (int yi = 0; yi < H; ++yi) {
        A[yi] = vector<char>(W);
    }
    for (int yi = 0; yi < H; ++yi) {
        string S;
        cin >> S;
        for (int xi = 0; xi < W; ++xi) {
            A[yi][xi] = S[xi];
        }
    }
    return A;
}

void OutputVec2d(vector<vector<ll>> A){
    for (int yi = 0; yi < A.size(); ++yi) {
        for (int xi = 0; xi < A[yi].size(); ++xi) {
            cout << A[yi][xi] << ",";
        }
        cout << endl;
    }
}

graph InputGraph(ll N,ll M){
    graph G(N);
    for (int i = 0; i < M; ++i) {
        ll a,b;
        cin >> a >> b;
        a--;b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    return G;
}
graph InputDGraph(ll N,ll M){
    graph G(N);
    for (int i = 0; i < M; ++i) {
        ll a,b;
        cin >> a >> b;
        a--;b--;
        G[a].push_back(b);
    }
    return G;
}

void OutputGraph(graph G){
    for (int i = 0; i < G.size(); ++i) {
        cout << i << ":";
        for (int j = 0; j < G[i].size(); ++j) {
            cout << G[i][j]<< ",";
        }
        cout << endl;
    }
}

void OutputAnswerBool(bool b,bool isUpperCase = false){
    if(b){
        if(isUpperCase){
            cout << "YES" << endl;
        }else{
            cout << "Yes" << endl;
        }
    }else{
        if(isUpperCase){
            cout << "NO" << endl;
        }else{
            cout << "No" << endl;
        }
    }
}

int main() {
    ll N;
    cin >> N;
    ll m = 1ll << 50;
    for (int i = 1; i < sqrt(N) + 2; ++i) {
        if( N % i == 0){
            ll a = i;
            ll b = N / i;
            ll ac = 0;
            ll bc = 0;
            while (a != 0){
                a /= 10;
                ac++;
            }
            while (b != 0){
                b/= 10;
                bc++;
            }
            m = min(m,max(ac,bc));
        }
    }
    cout << m << endl;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define pb push_back
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define F first
#define S second
#define MP make_pair
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

vector<pair<int,int>> st;
int arr[200005],n;

bool check(int x)
{
//	cout << ">" << x <<'\n';
	st.clear(),st.pb(MP(arr[0],1));
	for(int i=1;i<n;++i)
	{
		//for(auto i:st)
		//	cout << "(" << i.F << "," << i.S << ") ";
		//ET;
		if(st.back().F<arr[i]&&st.back().S!=1)
		{
			st.pb(MP(arr[i],1));
			continue;
		}
		if(st.back().S==1) 
			if(st.back().F<arr[i])
			{
				st.pop_back(),st.pb(MP(arr[i],1));
				continue;
			}
			else if(st.back().F==arr[i])
			{
				++st[st.size()-1].S;
				continue;
			}
			else st.pop_back();
		while(!st.empty()&&arr[i]<st.back().F) st.pop_back();
		if(st.empty()||st.back().F<arr[i])
		{
			st.pb(MP(arr[i],2));
			continue;
		}
		auto t=st.back();st.pop_back();
		if(t.S<x) ++t.S,st.pb(t);
		else
		{
			while(!st.empty())
			{
				if(st.back().F<t.F-1)
				{
					st.pb(MP(t.F-1,2));
					break;
				}
				t=st.back(),st.pop_back();
				if(t.S<x)
				{
					++t.S,st.pb(t);
					break;
				}
			}
			if(st.empty())
			{
				if(t.F==1) return 0; 
				st.pb(MP(t.F-1,2));
			}
		}
	}
//	for(auto i:st)
//		cout << "(" << i.F << "," << i.S << ") ";
	//ET;
	return 1;
}

int main()
{jizz
	int l=2,r,s=0;
	cin >> n,r=n;
	for(int i=0;i<n;++i)
		cin >> arr[i];
	for(int i=1;i<n;++i)
		if(arr[i]<=arr[i-1]) 
		{
			s=i;
			break;
		}
	if(s==0)
		return cout << "1\n",0;
	while(l<r)
	{
		int m=l+r>>1;
		if(check(m)) r=m;
		else l=m+1;
	}
	cout << l << "\n";
}

Measured memory_bytes: 1152
// AC

#include <bits/stdc++.h>
using namespace std;

#define INF 1000000001
typedef long long int ll;

int main()
{
  // INPUT
  int n,w; cin >> n >> w;
  int wt[n+1];
  ll  val[n+1];
  for(int i=0;  i<n; i++) cin >> wt[i+1] >> val[i+1];

  // INIT
  ll dp[w+1]={};

  // Base case already done: dp[0]=0;


  for(int i=1;i<=n;i++)
  {
    for(int k = w - wt[i]; k>=0; k--)
    {
      dp[k+wt[i]] = max(dp[k+wt[i]],dp[k]+val[i]);
    }
  }
  // OUTPUT
  ll answer = *max_element(dp,dp+w+1);
  cout << answer << endl;
}


Measured memory_bytes: 4388
#include<iostream>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<math.h>

using namespace std;

#define INF 1000000007
#define LINF (1LL << 62)

typedef long long i64;
typedef pair<i64,i64> P;


i64 n, m, k;

//コンビネーション
//けんちょんさんありがとう
const int MAX = 202020, MOD = INF;
long long fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; 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;
    }
}
// 二項係数計算
long long C(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
////

int main(){
	cin >> n >> m >> k;
	
	i64 ans = 0, cnt = 0;
	for(i64 i = 1; i < n; i++){
		cnt = i*(i+1) / 2 % INF;
		cnt = cnt * m % INF * m % INF;
		ans += cnt;
		ans %= INF;
	}
	for(i64 i = 1; i < m; i++){
		cnt = i*(i+1) / 2 % INF;
		cnt = cnt * n % INF * n % INF;
		ans += cnt;
		ans %= INF;
	}
	
	COMinit();
	cout << C(n*m-2, k-2) * ans % INF << endl;
	
	return 0;
}

Measured memory_bytes: 4992
#include <bits/stdc++.h>
#include <atcoder/all>
#define rep(i, n) for (int i = 0; i < (n); i++)
using ll = long long;
using namespace std;
using namespace atcoder;
using mint = modint1000000007;
int main() {
    int n,m;cin>>n>>m;
    vector<vector<int>> vec(n);
    rep(i,m){
        int a,b;cin>>a>>b;
        a--;b--;
        vec[a].push_back(b);
        vec[b].push_back(a);
    }
    vector<bool> v(n,0); 
    int ans=-1;
    rep(i,n){
        if(v[i]==1)continue;
        ans++;
        v[i]=1;
        queue<int> sta;
        sta.push(i);
        while(!sta.empty()){
            int to=sta.front();
            sta.pop();
            for(auto x:vec[to]){
                if(v[x]==1)continue;
                else {
                    sta.push(x);
                    v[x]=1;
                }
            }
        }
    }
    cout<<ans<<endl;
}

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

int main() {
    int sx,sy,tx,ty;
    cin >> sx >> sy >> tx >> ty;
    int dx = tx - sx;
    int dy = ty - sy;

    cout << string(dy, 'U') << string(dx, 'R');
    cout << string(dy, 'D') << string(dx, 'L');
    cout << 'L' << string(dy+1, 'U') << string(dx+1, 'R') << 'D';
    cout << 'R' << string(dy+1, 'D') << string (dx+1, 'L') << 'U';
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
typedef long long ll;
long long mod = 1e9 + 7;
const int iINF = 0x3f3f3f3f;
const long long INF = 1LL << 60;
using namespace std;

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

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

int main()
{
  int n;
  cin >> n;
  vector<int> a, b;
  rep(i, n)
  {
    int x, y;
    cin >> x >> y;
    a.push_back(x);
    b.push_back(y);
  }

  sort(a.begin(), a.end());
  sort(b.begin(), b.end());

  int ans = 0;

  if (n % 2 == 1)
  {
    int a_mid = a[a.size() / 2];
    int b_mid = b[b.size() / 2];
    ans = b_mid - a_mid + 1;
  }
  else
  {
    int a_mid = a[a.size() / 2 - 1] + a[a.size() / 2];
    int b_mid = b[b.size() / 2 - 1] + b[b.size() / 2];
    ans = b_mid - a_mid + 1;
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 5028
#include <iostream>
#include <cmath>

#define PI 3.14159265358979323846264338327950L
using namespace std;
int main(){
	long double a, b, h, m;
  	cin >> a >> b >> h >> m;
  	long double C = PI * 2 * (h/12.0 + (m/60.0)/12.0 - m/60.0);
  	long double val = pow(a, 2) + pow(b, 2) - 2*a*b*cos(C);
  	printf("%20.20Lf\n", sqrtl(val));
}


Measured memory_bytes: 4124
n = int(input())
a_list = list(map(int, input().split()))

m = 1000005

l = [0] * m


for a in a_list:
    # 0じゃなくなっていれば割り切れる値だということ
    if l[a] != 0:
        # 2以上なら割り切れることに変わりはないので2で固定
        l[a] = 2
        continue

    a_sub = a
    while a_sub < m:
        l[a_sub] += 1
        a_sub += a

# 割り切れない値の数を数える
ans = 0
for a in a_list:
    if l[a] == 1:
        ans += 1

print(ans)


Measured memory_bytes: 32256
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pu push
#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 SORT(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
void random(int x)
{
	int next=x;
	for(int i=0;i<10;i++)
	{
		next=next*next;
		int t=((next%1000000)-(next%100))/100;
		next=t;
		cout << next << endl;
	}
	return;
}
int main()
{
	int n;
	cin >> n;
	for(int i=0;i<n;i++)
	{
		printf("Case %d:\n",i+1);
		int k;
		cin >> k;
		random(k);
	}
	return 0;
}

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

#define vec              vector<int>
#define vecll            vector<ll>
#define vecd             vector<double>
#define vecst            vector<string>
#define vecb             vector<bool>
#define v2(v,n,m,init)   vector<vector<int>>  v(n, vector<int>(m, init))
#define vb2(v,n,m,init)  vector<vector<bool>> v(n, vector<bool>(m, init))
#define vll2(v,n,m,init) vector<vector<ll>>   v(n, vector<ll>(m, init))

#define rep(i,n)         for(ll i=(ll)0; i<(ll)n; i++)
#define REP(i,m,n)       for(ll i=(ll)m; i<(ll)n; i++)
#define arr(var, n)      vec var(n); rep(i,n){cin >> var[i];}
#define arrll(var, n)    vecll var(n); rep(i,n){cin >> var[i];}
#define arrst(var, n)    vecst var(n); rep(i,n){cin >> var[i];}
#define all(var)         (var).begin(), (var).end()
#define sortall(var)     sort(all(var))
#define uniqueall(v)     v.erase(unique(v.begin(), v.end()), v.end());
#define pb(var)          push_back(var)
#define prt(var)         cout << (var) << "\n"
#define prtd(n, var)     cout << fixed << setprecision(n) << (var) << "\n"
#define prtfill(n, var)  cout << setw(n) << setfill('0') << (var);
#define prt2(v1, v2)     cout << (v1) << " " << (v2) << "\n"
#define prt3(v1, v2, v3) cout << (v1) << " " << (v2) << " " << (v3) << "\n"
#define prtall(v)        rep(i,v.size()){cout<<v[i]<<(i!=v.size()-1?" ":"\n");}
template <typename T>
bool chmax(T &a, const T& b){if(a<b){a=b; return true;} return false;}
template <typename T>
bool chmin(T &a, const T& b){if(a>b){a=b; return true;} return false;}
//----------------------------------------------------------------

int main(void) {
  int a, b;
  cin >> a >> b;

  if(a%3==0 || b%3==0 || (a+b)%3==0){
    prt("Possible");
  } else {
    prt("Impossible");
  }

}


Measured memory_bytes: 3644
#include<stdio.h>

int main(){
    int t;
    scanf("%d", &t);
    
    int h, m ,s;
    
    h = t/3600;
    m = (t%3600)/60;
    s = t%60;
    
    printf("%d:%d:%d\n", h, m, s);
    
    return 0;
}


Measured memory_bytes: 2104
#pragma comment(linker, "/STACK:10240000")
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 110;
const long long MAX_INF = 0x3fffffff;

struct tnode
{
    long long x, y;
}a[MAXN];

long long x[MAXN], y[MAXN];

int main ()
{
    int n, k;
    scanf ("%d%d", &n, &k);
    for (int i = 1; i <= n; i ++)
    {
        scanf ("%lld%lld", &a[i].x, &a[i].y);
        x[i] = a[i].x;
        y[i] = a[i].y;
    }
    sort (x + 1, x + n + 1);
    sort (y + 1, y + n + 1);
    long long ans = (long long) 1 << 62;
    for (int i = 1; i < n; i ++)
    {
        for (int j = i + 1; j <= n; j ++)
        {
            for (int l = 1; l < n; l ++)
            {
                for (int r = l + 1; r <= n; r ++)
                {
                    int tmp = 0;
                    for (int k = 1; k <= n; k ++)
                    {
                        if ((a[k].x >= x[i]) && (a[k].x <= x[j]) && (a[k].y >= y[l]) && (a[k].y <= y[r]))
                        {
                            tmp ++;
                        }
                    }
                    if (tmp >= k)
                    {
                        long long now = (x[j] - x[i]) * (y[r] - y[l]);
                        if (now < ans)
                        {
                            ans = now;
                        }
                    }
                }
            }
        }
    }
    printf ("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <complex>
#include <utility>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#include <map>
#include <numeric>
#include <functional>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
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; }
inline void Yes(bool condition){ if(condition) PRINT("Yes"); else PRINT("No"); }
template<class itr> void cins(itr first,itr last){
    for (auto i = first;i != last;i++){
        cin >> (*i);
    }
}
template<class itr> void array_output(itr start,itr goal){
    string ans = "",k = " ";
    for (auto i = start;i != goal;i++) ans += to_string(*i)+k;
    if (!ans.empty()) ans.pop_back();
    PRINT(ans);
}
ll gcd(ll a, ll b) {
    return a ? gcd(b%a,a) : b;
}
const ll INF = 1e16;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
const ll MAX = 2510;
constexpr ll nx[8] = {1,0,-1,0,-1,-1,1,1};
constexpr ll ny[8] = {0,1,0,-1,-1,1,-1,1};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,k;
    cin >> n >> k;
    int ans = k*pow(k-1,n-1);
    PRINT(ans);
}


Measured memory_bytes: 256
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin

for line in stdin:
    L = [int(c) for c in line.strip()]
    while len(L) > 1:
        L = [(L[i] + L[i + 1]) % 10 for i in range(len(L) - 1)]
    print(L[0])

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

#define int long long
#define rep(x,y) for(int i=x;i<y;i++)
#define REP(x,y) for(int j=x;j<y;j++)
#define str string
#define vint vector<int>
#define vchar vector<char>
#define vool vector<bool>
#define pb() pushback
#define elif else if

main(){
    int N,a,b,count=0,count2=0;
    double r,pai=3.141592653589;
    int C='A'-'a';
    char op;
    str S,T;
    while(1){
      cin>>a>>op>>b;
      if(op=='+')cout<<a+b<<endl;
      elif(op=='-')cout<<a-b<<endl;
      elif(op=='*')cout<<a*b<<endl;
      elif(op=='/')cout<<a/b<<endl;
      else break;
    }
}



Measured memory_bytes: 3076
from collections import Counter
mod = 1000000007


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


def main():
    m, d=map(int, input().split())
    ans = 0
    for i in range(1, m+1):
        for j in range(1, d+1):
            a = str(j)
            if len(a) != 2:
                continue
            b = 1
            for k in a:
                b *= int(k)
            if i == b and a[0] != '1' and a[1] != '1':
                # print(i, j)
                ans += 1

    print(ans)
main()


Measured memory_bytes: 3444
import heapq
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')

N, K = LI()
S = str(input())
ans = int(0)

R = []
L = []
before = "R"
if S[0]=="L":
    R.append(0)
    before = "L"
cur = int(0)
for s in S:
    if before==s:
        cur +=1
    else:
        if s=="L":
            R.append(cur)
            before = "L"
            cur = int(1)
        else:
            L.append(cur)
            before = "R"
            cur = int(1)

if s == "L":
    L.append(cur)
else:
    R.append(cur)

#print(R,L)
Rlen = len(R)
Llen = len(L)
#ansC = []
#for i in range(Rlen-K):
#    cur = int(0)
#    for j in range(K+1):
#        cur += R[i+j]
#    for j in range(K):
#        cur += L[i+j]
#    ansC.append(cur)
#for i in range(Llen-K):
#    cur = int(0)
#    for j in range(K):
#       cur += R[i+j+1]
#    for j in range(K+1):
#        cur += L[i+j]
#    ansC.append(cur)
#print(ansC)

ans = min(N-1, 2*K+sum(R)+sum(L)-Rlen-Llen)
if S[0]=="L":
    ans +=1
ans = min(N-1,ans)
print(ans)


Measured memory_bytes: 44272
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;

void ABC166E()
{
	int N;
	cin >> N;
	vi A(N);
	for (auto& x : A)
		cin >> x;
	map<int, int> sum;
	ll ans = 0;
	for (int i = 0; i < N; ++i)
	{
		int diff = (i + 1) - A[i];
		auto p = sum.find(diff);
		if (p != sum.cend())
			ans += p->second;
		++sum[(i + 1) + A[i]];
	}
	cout << ans << endl;
}

int main()
{
	ABC166E();
	return 0;
}


Measured memory_bytes: 13136
import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
import std.range;
import std.container;
import std.bigint;
import std.math;

double cross (cdouble a, cdouble b) {
	return (a * b.conj).im;
}

void main()
{
	int n = readln.chomp.to!int;
	foreach (i; 0..n) {
		auto p = readln.split.map!(to!double);
		auto a = p[2] - p[0] + (p[3] - p[1]) * 1i;
		auto b = p[6] - p[4] + (p[7] - p[5]) * 1i;
		if (cross(a, -b).abs < 1e-12) writeln("YES");
		else writeln("NO");
	}
}

Measured memory_bytes: 1112
#pragma warning(disable:4996)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <float.h>

#pragma region 定義
typedef long long  ll;
typedef unsigned long long  ull;


#define _itoa(A,N) sprintf(A, "%d", N);

int i_dsort(const void* a, const void* b);
int i_asort(const void* a, const void* b);

int  _gcd(int a, int b);
int  _swp(int* a, int* b);
int _cknum(char* a, int n);
int _atoi(char* s, int len);

int s_asort(const void* a, const void* b);
int s_dsort(const void* a, const void* b);

//昇順
int s_asort(const void* a, const void* b) {
	return(strcmp((char*)a, (char*)b));
}
int s_dsort(const void* a, const void* b) {
	return(strcmp((char*)b, (char*)a));
}

int i_dsort(const void* a, const void* b) {
	return(*(int*)b - *(int*)a);
}
int i_asort(const void* a, const void* b) {
	return(*(int*)a - *(int*)b);
}

int _gcd(int a, int b) {
	int r, tmp;
	if (a < b) { tmp = a; a = b; b = tmp; }
	r = a % b;
	while (r) {
		if (!r) break;
		a = b; b = r;
		r = a % b;
	}
	return(b);
}
// puts("Yes\n") puts("No\n")
// scanf("%d.%d") 浮動小数点入力を整数２つで得る


//#define pai  3.1415926535 
//#define  _USE_MATH_DEFINES でM_PIが使える

#define deg_rad(X)  (X*(M_PI/180))


int _swp(int* a, int* b)
{
	int tmp;
	tmp = *b; *b = *a; *a = tmp;
	return 0;
}
#define _abs(x) ((x)>0?(x):-(x))
#define _min(x,y) ((x)<(y)?(x):(y))
#define _max(x,y) ((x)<(y)?(y):(x))

int _cknum(char* a, int n) {
	int i;
	char t = '0';

	for (i = 0; i < n; i++) {
		if (a[i] < '0' || a[i]>'9') return 1;
	}
	return 0;
}


int _atoi(char* s, int len) {
	char tmp[20];
	memcpy(tmp, s, len);
	tmp[len] = 0x00;
	return (atoi(tmp));
}

//素因数分解　pf素数が入る　pc 素数の数
ll _pfact(ll a);
static ll pf[100000000];
static ll pc;

ll _pfact(ll a) {
	long i, r;
	if (a % 2 == 0) {
		pf[pc] = 2; pc++;
		return(_pfact(a / 2));
	}
	r = sqrt(a);
	for (i = 3; i <= r; i += 2) {
		if (a % i == 0) {
			pf[pc] = i; pc++;
			return(_pfact(a / i));
		}
	}
	if (a != 1) {
		pf[pc] = a; pc++;
	}
	return 0;

}


#pragma endregion



//ANC  171 D
#define MAX 100001
static int a[MAX];
static ll  t[MAX];
int main(void) {
	int n, q, i, p;
	ll sum=0;

	scanf("%d", &n);

	//printf("\n");
	for (i = 0; i < n; i++) {
		scanf("%d", &p);
		sum += (ll)p;
		a[p - 1]++;
	}

	scanf("%d", &q);
	int b, c;

	ll tt;
	for (i = 0; i < q; i++) {
		scanf("%d %d", &b, &c);
		tt = 0;
		if (a[b - 1] == 0) {
			printf("%lld\n", sum);
			continue;
		}
		tt = ((ll)c - (ll)b) * (ll)a[b - 1];
		sum += tt;
		printf("%lld\n", sum);
		a[c - 1] += a[b - 1];
		a[b - 1] = 0;
	}


//	for (i = 0; i < q; i++) {
//		printf("t[%d]:%d \n",i,t[i]);
//		sum += t[i];
//		printf("%lld\n", sum);
//	}
	return 0;
}


//ABC  171 C

//int main(void) {
//	

//	return 0;
//}


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

using namespace std;
typedef unsigned int ui;

int main(void)
{
	ui max_n, max_w;
	ui v, w;

	cin >> max_n >> max_w;
	vector<ui> table(max_w+1, 0);
	for(int i = 1; i <= max_n; ++i){
		cin >> v >> w;
		for(int j = max_w-w; j >= 1; --j){
			if(table[j] != 0 && table[w+j] < table[j] + v)
				table[w+j] = table[j] + v;
		}
		if(w <= max_w && table[w] < v)
			table[w] = v;
	}

	cout << *(max_element(begin(table), end(table))) << endl;
}

Measured memory_bytes: 1228
def main():
    X, K, D = map(int, input().split())
    if X < 0:
        X = -X
    num_of_moves = min(X // D, K)

    X -= D * num_of_moves
    K -= num_of_moves

    K %= 2

    ans = abs(X - D * K)

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9196
#include<bits/stdc++.h>
#include<vector>
#include<set>
#include<algorithm>

using namespace std;

#define rep(i,n) for(int i=0; i<(n); i++)
#define T int t, q=0; scanf("%d", &t); while(q++<t)
#define ll long long
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
ll x,y,z,a=0,b=0,c=0,d=0,sum,ans,total,cnt,n,m,k,p,kase,i,t;
string s1,s2;
#define N 100001
#define MX 1000000001
vector <ll> v;
map<ll,ll> mp;
set<ll> s;
map<ll,ll> :: iterator itr1, ptr1;
set<ll> :: iterator itr, ptr;


int main()
{


        cin>>n>>x>>t;

        ans=0;
        sum=0;
        while(1)
        {
            ans+=t;

            sum+=x;

            if(sum>=n)break;

        }
        cout<<ans;




    return 0;
}
// Happy Coding  (:


Measured memory_bytes: 3632
n = int(input())
a = [0] + list(map(int, input().split()))
alive = [1 for i in range(n + 1)]
sol = sum(a)
while True:
    pot = []
    change = False
    for i in range(n, 0, -1):
        if a[i] >= 0 or alive[i] == 0:
            continue
        saldo = 0
        j = i
        while j <= n:
            saldo += alive[j] * a[j]
            j += i
        if saldo > 0:
            pot.append(i)
            continue
        change = True
        sol -= saldo
        j = i
        while j <= n:
            alive[j] = 0
            j += i
    if change:
        continue
    k = len(pot)
    for i in range(k):
        if change: break
        for j in range(i):
            saldo = 0
            for v in range(1, n + 1):
                if v % pot[i] == 0 or v % pot[j] == 0:
                    saldo += alive[v] * a[v]
            if saldo <= 0:
                change = True
                sol -= saldo
                for v in range(1, n + 1):
                    if v % pot[i] == 0 or v % pot[j] == 0:
                        alive[v] = 0
                break
    if not change:
        break
print(sol)


Measured memory_bytes: 3064
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <stack>
#include <set>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define INF (int)(1123456789)
#define LINF (long long int)(112345678901234567)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define all(v) v.begin(), v.end()

const int N = 1234567;

ll mpow(ll a, ll b){
	if(b==0) return 1;
	else if(b%2==0){ll memo = mpow(a,b/2); return memo*memo%MOD;}
	else return mpow(a,b-1) * a % MOD;
}
ll gcd(ll a, ll b){
	if(b==0) return a;
	else return gcd(b, a%b);
}
vector<ll> kaijo_memo;
ll kaijo(ll n){
	if(kaijo_memo.size() > n) return kaijo_memo[n];
	if(kaijo_memo.size() == 0) kaijo_memo.push_back(1);
	while(kaijo_memo.size() <= n) kaijo_memo.push_back(kaijo_memo[kaijo_memo.size()-1] * kaijo_memo.size() % MOD);
	return kaijo_memo[n];
}
ll nCr(ll n, ll r){
	if(n < r || r < 0) return 0;
	ll ret = 1;
	ret *= kaijo(n); ret %= MOD;
	ret *= mpow(kaijo(r), MOD-2); ret %= MOD;
	ret *= mpow(kaijo(n-r), MOD-2); ret %= MOD;
	return ret;
}

int s_pow(int a, int b){
	if(b >= 20){
		return 10000;
	}else{
		return pow(a,b);
	}
}

int main(void){
	int n,k;
	cin>>n>>k;
	string s;
	cin>>s;
	string t = s;
	reverse(all(t));
	s += t;

	vector<string> kouho;
	rep(i,n){
		kouho.push_back(s.substr(i,n));
	}
	sort(all(kouho));

	char a = kouho[0][0];
	string ans = "";
	int i = 0;
	while(ans.size() < n && kouho[0][i] == a){
		for(int j=0; j < pow(2,min(20, k-1)) && ans.size() < n; j++){
			ans.push_back(a);
		}
		i++;
	}
	while(ans.size() < n){
		ans.push_back(kouho[0][i]);
		i++;
	}

	cout<<ans<<endl;

	return 0;
}


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


int main()
{
  int n ;
  cin>>n;
  string s;
  cin>>s;
  int x=0;
  int ans=0;
  for(int i=0;i<n;i++)
  {
      if( s[i] =='I')
      {
          x++;
          ans = max( ans , x);
      } else
      {
          x--;
          ans = max( ans , x);
      }
  }
  cout<<ans;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define CLR(a,x) memset(a,x,sizeof(a))
#define MP make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pa;
const int maxn=1e5+10;

inline ll rd(){
    ll x=0;char c=getchar();int neg=1;
    while(c<'0'||c>'9'){if(c=='-') neg=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*neg;
}

int N,eg[maxn*2][3],egh[maxn],ect;
int siz[maxn];
ll sum,n0,ans;

inline void adeg(int a,int b,int c){
	eg[++ect][0]=b,eg[ect][1]=egh[a],egh[a]=ect,eg[ect][2]=c;
}

inline void dfs(int x,int f,int ine){
	siz[x]=1;
	for(int i=egh[x];i;i=eg[i][1]){
		int b=eg[i][0];if(b==f) continue;
		dfs(b,x,i);siz[x]+=siz[b];
		n0+=eg[i][2]*(siz[b]>=N-siz[b]);
	}
	sum+=2ll*min(siz[x],N-siz[x])*eg[ine][2];
}

inline void dfs2(int x,int f,ll n){
	if(sum-n>ans&&n) ans=sum-n;
	for(int i=egh[x];i;i=eg[i][1]){
		int b=eg[i][0];if(b==f) continue;
		dfs2(b,x,n+eg[i][2]*((siz[b]<=N-siz[b])-(siz[b]>=N-siz[b])));
	}
}

int main(){
    //freopen("","r",stdin);
	N=rd();
	for(int i=1;i<N;i++){
		int a=rd(),b=rd(),c=rd();
		adeg(a,b,c),adeg(b,a,c);
	}
	dfs(1,0,0),dfs2(1,0,n0);
	printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 5632
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pp pair<pair<ll, ll>,pair<ll, ll>>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define vii vector<int>
#define vll vector<ll>
#define mat vector<vector<ll>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define fi first
#define sc second
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (ll) (x).size()
#define pq priority_queue<ll>
#define pqg priority_queue<ll,vector<ll>,greater<ll>>
#define LB(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define UB(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
#define ERASE(v) sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end())
#define int ll
using namespace std;
const ll INF = (1 << 30 ) - 1;
const ll LLINF = (1LL << 60LL);
const ll MOD = 1000000007;
const ll mod = 998244353;
const ll MAX = 1100000;
const double pi = acos(-1);
const double eps = 1e-10;
ll dx[4] ={1,0,-1,0} , dy[4] ={0,1,0,-1};
 
template<class T> 
inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> 
inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
 
struct Timer{
    chrono::system_clock::time_point start, end;
    Timer(){ start = chrono::system_clock::now(); }
    ~Timer(){
        end = chrono::system_clock::now();
        auto msec = chrono::duration_cast<chrono::milliseconds>(end - start).count();
        cerr<<"time : "<<msec<<" ms"<<endl;
    }
};


signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Timer TM;

    ll a,b,k;
    cin>>a>>b>>k;
    if(a>k) a-=k;
    else{
        k-=a;
        a=0;
        b=max(0ll,b-k);
    }
    cout<<a<<" "<<b<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int n,m;
  cin>>n>>m;
  int h[n];
  int x[n];
  for(int i=0;i<n;i++){
    cin>>h[i];
    x[i]=1;
  }
  for(int i=0;i<m;i++){
    int a,b;
    cin>>a>>b;
    if(h[a-1]<h[b-1]){
      x[a-1]=0;
    }
    if(h[a-1]>h[b-1]){
      x[b-1]=0;
    }
    if(h[a-1]==h[b-1]){
      x[a-1]=0;
      x[b-1]=0;
    }
  }
  int ans=0;
  for(int i=0;i<n;i++){
    if(x[i]==1){
      ans++;
    }
  }
  cout<<ans;
  return 0;
}

Measured memory_bytes: 4408
s = str(input())

cnt_1 = 0
cnt_2 = 0

for i in range(len(s)):
    if i%2 == 0:
        if s[i] == "1":
            cnt_1 += 1
        else:
            cnt_2 += 1
    else:
        if s[i] == "0":
            cnt_1 += 1
        else:
            cnt_2 += 1
print(min(cnt_1, cnt_2))

Measured memory_bytes: 3188
#include <iostream>
#include <vector>
using namespace std;
const int mod = 1000000007;
int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i = 0; i < n; i++){
    cin >> a[i];
  }
  int x = 0;
  int ans = 0;
  for(int i = 0; i < n; i++){
    ans = (ans + (long long)a[i] * x) % mod;
    x = (x + a[i]) % mod;
  }
  cout << ans;
  return 0;
}


Measured memory_bytes: 4048
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007

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

  int ans = 0;
  for(int i = 0;i < 4;i++) {
    if(N % 10 == 2) ans++;
    N /= 10;
  }

  cout << ans << endl;
}



Measured memory_bytes: 256
// Jai Sai Ram
//Always help me!
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
vector<ll> adj[300001];
ll vis[1000001];
ll dis[1000001];
ll eig[1000001];
ll P=1e9+7;
void solve()
{
    ll i,j,k,l,m,n,o,p,q,r,t,a,b,c,d;
    cin>>n;
    dis[0]=1;
    eig[0]=1;
    vis[0]=1;
    for(i=1;i<=1000000;i++)
    {
        dis[i]=(dis[i-1]*10)%P;
        vis[i]=(vis[i-1]*9)%P;
        eig[i]=(eig[i-1]*8)%P;
    }
    if(n==1)
    {
        cout<<0<<endl;
        return ;
    }
    else 
    {
        i=n;
        cout<<(dis[i]+eig[i]-(2*vis[i])+10*P)%P;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
     cin.tie(0);
    ll t=1;
   // cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}


Measured memory_bytes: 34120