akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

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


void solve() {
    int i,j,k,l,r,x,y; string s;
    bool exit = false;
    string S;
    cin>>S;
    
    int N = S.length();
    vector<int> cnt(N);
    int cnt_B=0;
    FOR(i,N){
        if(S[i]=='B'){
            cnt[i]=0;
            cnt_B+=1;
            //cout<<"in B"<<endl;
        }else{
            cnt[i]=cnt_B;
        }
    }
    ll ret=0;
    FORR(x, cnt){
        ret+=x;
        //cout<<x<<endl;
    }
    cout<< ret <<endl;    
    /*cin>>N;
    vector<ll> V((N+1)*(N+1));
    FOR(x,N+1) {
            FOR(y,N+1) {
                    ll ret=1;
                    FOR(i,x) ret*=2;
                    FOR(i,y) ret*=5;
                    V.push_back(ret);
            }
    }
    sort(ALL(V));
    FORR(v,V) cout<<v<<endl;*/
}


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



Measured memory_bytes: 1428
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll mod=1000000007, inf = 1000000007;
int main() {
	ll i,j,k,l,m,n,t;
	ios_base::sync_with_stdio(false);
  cin.tie(NULL);
	t=1;
	while(t--)
	{
		cin>>n;
		ll a[n];
    vector<ll> ans(n, inf);
    for (i = 0; i < n; i++)
    {
			cin>>a[i];
		}
    ans[0] = 0;
    for (i = 0; i < n - 1; i++)
    {
      if(i+2<n){
        ans[i + 2] = min(ans[i + 2], abs(a[i]-a[i+2])+ans[i]);
      }
      ans[i + 1] = min(ans[i + 1], abs(a[i]-a[i+1])+ans[i]);
    }
    cout << ans[n - 1] << endl;
  }
  return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;
using P = pair<int, int>;
long mod = (long) 1e9 + 7;

int main(){
    
    int n, m;
    cin >> n >> m;
    
    int p = n / 2;
    
    if(n % 2 > 0){
        int head = 1, tail = n;
        rep(i,m){
            cout << head << ' ' << tail << "\n";
            head++;
            tail--;
        }
        
    }else {
        int head = 1, tail = n;
        rep(i,m){
            cout << head << ' ' << tail << "\n";
            head++;
            tail--;
            if (i == n / 4 - 1) tail--;
        }
        
    }
    
    return 0;
}



Measured memory_bytes: 3124
N,M,K = list(map(int,input().split()))
import sys
input = sys.stdin.readline
from collections import defaultdict
class UF():
  def __init__(self,n):
    self.n_node = n
    self.l = [i for i in range(n)]
    self.size = [1 for i in range(n)]
    self.d = None
  
  def union(self,i,j):
    if not self.connected(i,j):
      iroot,ipath = self.root(i,return_path=True)
      jroot,jpath = self.root(j,return_path=True)
      if len(jpath) < len(ipath):
        for node in ipath + jpath:
          self.l[node] = iroot
      else:
        for node in ipath + jpath:
          self.l[node] = jroot
        
  def root(self,i,return_path=False):
    path = [i]
    while self.l[i] != i:
      i = self.l[i]
      path.append(self.l[i])
    
    if return_path:
      return i,path
    else:
      return i
  
  def connected(self,i,j):
    if self.root(i) == self.root(j):
      return True
    else:
      return False
  
  def simplify(self):
    for node in range(self.n_node):
      root = self.root(self.l[node])
      if self.l[node] != root:
        self.l[node] = root
  
  def calc_connected(self):
    self.d = defaultdict(set)
    self.simplify()
    for idx,root in enumerate(self.l):
      self.d[root] |= {idx}
    
  def connected_set(self,i):
    if self.d is None:
      self.calc_connected()
    return self.d[self.root(i)]
      
uf = UF(N)
direct_connected = defaultdict(set)
for i in range(M):
  i,j = map(int,input().split())
  i-=1
  j-=1
  
  uf.union(i,j)
  direct_connected[i] |= {j}
  direct_connected[j] |= {i}

block_list = defaultdict(set)
for i in range(K):
  i,j = map(int,input().split())
  i-=1
  j-=1
  if uf.connected(i,j):
    block_list[i] |={j}
    block_list[j] |={i}

  
uf.calc_connected()
for i in range(N):
  print(len(uf.d[uf.l[i]]) - len(direct_connected[i]) - len(block_list[i])-1,end=" ")


Measured memory_bytes: 128204
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
int n;
vector<pair<int,int> >a;
vector<int>A;
map<int,int>M;
int cnt[2<<17];
main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		int s,t;cin>>s>>t;
		a.push_back(make_pair(s,t));
		A.push_back(s);
		A.push_back(t);
	}
	sort(A.begin(),A.end());
	A.erase(unique(A.begin(),A.end()),A.end());
	int sz=0;
	for(int i=0;i<A.size();i++)M[A[i]]=sz++;
	for(int i=0;i<n;i++)
	{
		cnt[M[a[i].first]]++;
		cnt[M[a[i].second]+1]--;
	}
	int ans=cnt[0];
	for(int i=1;i<2<<17;i++)ans=max(ans,cnt[i]+=cnt[i-1]);
	cout<<ans<<endl;
}



Measured memory_bytes: 14888
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vvi vector<vi>
#define vs vector<string>
#define pb push_back
#define P pair<int,int>
#define vp vector<P>
#define PP pair<int,P>
#define vpp vector<PP>
#define fi first
#define se second
#define INF 1e9
#define MOD 1000000007
#define REP(i,n) for(int i=0;i<n;i++)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define all(x) (x).begin(),(x).end()
int main(){
    int a,b,x;
    cin>>x>>a>>b;
    cout<<(x-a)%b<<endl;
    return 0;
}

Measured memory_bytes: 256
tmp = list(map(int, input().split()))
n = tmp[0]
k = tmp[1]
s = input()

sl = []
for i in range(len(s)):
  if i == k-1:
    if s[i] == 'A':
      sl.append('a')
    elif s[i] == 'B':
      sl.append('b')
    else:
      sl.append('c')
  else:
    sl.append(s[i])

print (''.join(sl))

Measured memory_bytes: 38256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll longinf = 1LL << 60;
const ll mod = 1e9 + 7;

#define INF 1LL << 60
#define MAX_V 100010

struct edge {
    ll to;
    ll cost;
};

// <最短距離, 頂点の番号>
using P = pair<ll, ll>;

ll V;
vector<edge> G[MAX_V];
ll d[MAX_V];

void dijkstra(ll s) {
    priority_queue<P, vector<P>, greater<P> > que;
    fill(d, d + V, INF);
    d[s] = 0;
    que.push(P(0, s));

    while(!que.empty()) {
        P p = que.top();
        que.pop();
        ll v = p.second;
        if(d[v] < p.first) continue;

        for(int i = 0; i < G[v].size(); ++i) {
            edge e = G[v][i];
            if(d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to], e.to));
            }
        }
    }
}

int main() {
    int N;
    cin >> N;
    V = N;
    for(int i = 0; i < N - 1; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        a--;
        b--;
        G[a].push_back({b, c});
        G[b].push_back({a, c});
    }
    ll Q, K;
    cin >> Q >> K;
    K--;
    dijkstra(K);
    for(int i = 0; i < Q; i++) {
        ll x, y;
        cin >> x >> y;
        x--;
        y--;
        cout << d[x] + d[y] << "\n";
    }
    return 0;
}


Measured memory_bytes: 11776
#include<stdio.h>
#include<stdlib.h>

#define WHITE 0
#define GRAY 1
#define BLACK 2
#define INFTY 10000

int n;
int **mat;

int prim();

int main(){
  int i,j;

  scanf("%d",&n);

  mat = (int **)malloc(n * sizeof(int *));
  for(i=0; i<n; i++)
    mat[i] = (int *)malloc(n * sizeof(int));

  for(i=0; i<n; i++){
    for(j=0; j<n; j++){
      scanf("%d",&mat[i][j]);
    }
  }

  printf("%d\n",prim());
  
  for(i=0; i<n; i++)
    free(mat[i]);
  free(mat);
  return 0;
}

int prim(){
  int *color, *d;
  int mincost;
  int u,v;
  int sum=0;
  int i;
  
  color = (int *)malloc(n * sizeof(int));
  d = (int *)malloc(n * sizeof(int));

  for(i=0; i<n; i++){
    color[i] = WHITE;
    d[i] = INFTY;
  }

  d[0] = 0;

  while(1){
    mincost = INFTY;

    for(i=0; i<n; i++){
      if(color[i]!=BLACK && d[i]<mincost){
	mincost = d[i];
	u = i;
      }
    }

    if(mincost == INFTY)
      break;

    color[u] = BLACK;

    for(v=0; v<n; v++){
      if(color[v]!=BLACK && mat[u][v]!=-1){
	if(mat[u][v] < d[v]){
	  d[v] = mat[u][v];
	  color[v] = GRAY;
	}
      }
    }
  }

  for(i=0; i<n; i++){
    sum += d[i];
  }

  free(color);
  free(d);
  return sum;
}



Measured memory_bytes: 2112
import java.io.PrintWriter;
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int a = Integer.parseInt(sc.next());
        int b = Integer.parseInt(sc.next());
        int c = Integer.parseInt(sc.next());
        int k = Integer.parseInt(sc.next());
        out.println(Math.min(a, k) - Math.max(k - a - b, 0));
        out.flush();
    }
}

Measured memory_bytes: 35752
#include <bits/stdc++.h>
 
using namespace std;
 
#define debug(a) cerr << #a << ": " << a << endl
 
typedef long long ll;
typedef pair<int, int> ii;
 
#define x first
#define y second
 
const int N = 2e5 + 10;

ll n;
ll x[N];
ll X;
ll pref[N];

ll solve(ll len) {
	ll ret = 0LL;
	ll cnt = 1LL;

	ret += (pref[n] - pref[n - len]);
	
	for (ll r = n; r > 0; r -= len, cnt++) {
		ll l = max(0LL, r - len);
		
		ll add;
		add = ((pref[r] - pref[l]) - x[l] * (r - l)) * (cnt + 1) * (cnt + 1);
		if (add < 0) return LLONG_MAX;
		ret += add;
		if (ret < 0) return LLONG_MAX;
		if (r < n) {
			add = (x[r] * len - (pref[r] - pref[l])) * cnt * cnt;
			if (add < 0) return LLONG_MAX;
			ret += add;
			if (ret < 0) return LLONG_MAX;
		}
	}

	ret += X * n;
	if (ret < 0) return LLONG_MAX;
	ret += X * len;
	if (ret < 0) return LLONG_MAX;

	return ret;
}

int main() {
	#ifdef LOCAL
	freopen("in", "r", stdin);
	freopen("out", "w", stdout);
	#endif
 
	cin >> n >> X;
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &x[i]);
		pref[i] = pref[i - 1] + x[i];
	}

	ll ans = LLONG_MAX;
	for (int i = 1; i <= n; i++) {
		ans = min(ans, solve(i));
	}

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

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

int main() {
  int N;
  int K;
  int w;
  cin >> N;
  cin >> K;
  vector<int> p(N);
  for ( int i = 0; i < N; i++){
    cin >> p.at(i);
  }
  w = 0;
  sort(p.begin(), p.end());
  for ( int i = 0; i < K; i++){
    w = w + p.at(i);
  }
  
  cout << w << endl;
}

Measured memory_bytes: 3596
X, N = map(int,input().split(' '))
if N == 0:
    print(X)
    exit()

p = input().split(' ')
p =[int(i) for i in p]
if X not in p:
    print(X)
    exit()

num_list = [int(i) for i in range(102)]
[num_list.remove(p[i]) for i in range(N)]
tmp = [0] * int(len(num_list))


for i in range(len(num_list)):
    tmp[i] = abs(num_list[i] - X)

ans = tmp.index(min(tmp))

print(num_list[ans])


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

//l-child, r-sibling representation

int n;
int p[100010]; //parent
int l[100010]; //left-child
int r[100010]; //right-sibling

void dfs(int n, int depth){ //calculate the depth
  if(p[n] == -1){ //if the node n does't have parent, that is root
    cout << "depth = " << depth << ", "; //a depth is a distance from root to node n 
    return ;
  }

  dfs(p[n], depth + 1); //if the node n isn't root, continue to search depth recursively
  return ;
}

void searchchild(int c){
  cout << '[';
  for(int i = 0;;i++){
    if(c == -1) break; //if node c doesn't have sibling, finish searching
    cout << (i?", ":"");
    cout << c;
    c = r[c]; //sibling is stored right
  }
  cout << ']' << endl;
}

void searchtype(int i){
  if(p[i] == -1) cout << "root, "; //if the node i doesn't have parent, that node is root
  else if(l[i] != -1) cout << "internal node, "; //if the node i have a child, that node is internal node
  else cout << "leaf, "; // if the node i doesn't have child, that node is leaf
}

void solve(){ //output function
  for(int i = 0;i < n;i++){
    cout << "node " << i << ": ";
    cout << "parent = " << p[i] << ", ";
    dfs(i, 0);
    searchtype(i);
    searchchild(l[i]);
  }
}

int main(){

  //input
  cin >> n;
  for(int i = 0;i < n;i++) p[i] = l[i] = r[i] = -1;
  for(int i = 0;i < n;i++){
    int id, k, c, s;

    cin >> id >> k;
    for(int j = 0;j < k;j++){
      cin >> c;
      if(j == 0) l[id] = c;
      else r[s] = c;
      p[c] = id;
      s = c;
    }
  }

  //output
  solve();

  return 0;
}




Measured memory_bytes: 4268
N = int(input())
A = list(map(int, input().split()))
S = 0
h = A[0]

for i in range(1, len(A)):
  if A[i] < h:
    S += (h - A[i])
    h = max(h, A[i-1])
  else:
    h = A[i]

print(S)

Measured memory_bytes: 32192
import java.util.*;

public class Main {

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

        String s = sc.next(), t = sc.next();

        if (!exists(s, t)) {
            System.out.println(-1);
            return;
        }

        HashMap<Character, ArrayList<Integer>> map = new HashMap<>();
        HashMap<Character, Integer> lens = new HashMap<>();

        int n = s.length();
        for (int i = 0; i < n; i++) {
            ArrayList<Integer> l = map.getOrDefault(s.charAt(i), new ArrayList<>());
            l.add(i);
            map.put(s.charAt(i), l);
            lens.put(s.charAt(i), lens.getOrDefault(s.charAt(i), 0) + 1);
        }

        int m = t.length();

        long len = 0;
        int cur = -1;

        for (int i = 0; i < m; i++) {
            char c = t.charAt(i);
            ArrayList<Integer> l = map.get(c);
            int idx = lowerBound(l, cur + 1);
            if (idx == lens.get(c)) {
                len = ((len - 1) / n + 1) * n;
                idx = lowerBound(l, 0);
                cur = l.get(idx);
                len += l.get(idx) + 1;

//                debug("1", l.get(idx), cur, len);
            } else {
                len += l.get(idx) - cur;
                cur = l.get(idx);

//                debug("2", l.get(idx), cur, len);
            }
        }
        System.out.println(len);
    }

    boolean exists(String s, String t) {
        HashSet<Character> exists = new HashSet<>();
        int n = s.length();
        for (int i = 0; i < n; i++) exists.add(s.charAt(i));

        int m = t.length();
        for (int i = 0; i < m; i++) if (!exists.contains(t.charAt(i))) {
            return false;
        }
        return true;
    }

    public int lowerBound(ArrayList<Integer> array, int value) {
        int left = -1;
        int right = array.size();
        while (right - left > 1) {
            int middle = (right + left) / 2;
            if (array.get(middle) >= value) {
                right = middle;
            } else {
                left = middle;
            }
        }
        return right;
    }

    public int upperBound(int[] array, int value) {
        int left = -1;
        int right = array.length;
        while (right - left > 1) {
            int middle = (right + left) / 2;
            if (array[middle] > value) {
                right = middle;
            } else {
                left = middle;
            }
        }
        return right;
    }

    void debug(Object... os) {
        System.err.println(Arrays.deepToString(os));
    }

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

}


Measured memory_bytes: 33164
#関数リスト
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

q = I()
mylist = LI()
result = 0
for i in mylist:
    result = result ^ i

for i in mylist:
    print(result ^ i)

Measured memory_bytes: 104980
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define l long
#define pb push_back
#define mp make_pair
#define mt make_tuple
int main() {
	// your code goes here
	//ifstream cin("input.txt");
	//ofstream cout("output.txt");
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
	cout<<fixed<<setprecision(14);
	double r; cin>>r;
	double ans = 2*3.141592653589793*r;
	cout<<ans;
	
	return 0;
}

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

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int x, y;
	scanf("%d %d", &x, &y);

	bool is_positive;
	if (abs(y) - abs(x) > 0) {
		is_positive = true;
	} else {
		is_positive = false;
	}

	int count = 0;
	if ((x > 0 != is_positive) && x != 0) {
		count++;
	}
	if ((y > 0 != is_positive) && y != 0) {
		count++;
	}
	printf("%d", count + abs(abs(y) - abs(x)));
	return 0;
}

Measured memory_bytes: 512
N,x = map(int,input().split())
*A, = map(int,input().split())
c = [A[:] for _ in [0]*(N)]
ans = sum(A)
for i in range(1,N):
    for j in range(N):
        c[i][j] = min(c[i-1][j-1],c[i][j])
    ans = min(ans,sum(c[i])+x*i)
print(ans)

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

using namespace std;

int main () {
    int r,c;
    int tec=0;
    cin>>r>>c;
    int ave[r][c];
    
    for(int s=0;s<r; s++)
    {
        for(int t=0; t<c; t++)
        {
            cin>>ave[s][t];
        }
    }
        for(int s=0;s<r; s++)
        {
            int num=0;
            for(int t=0; t<c; t++)
            {
                cout<<ave[s][t]<<" ";
                num+=ave[s][t];
            }
            cout<<num;
            cout<<endl;
        }
    for(int m=0; m<c; m++)
    {int st=0;
        for(int w=0;w<r; w++)
        {
            st += ave[w][m];
            tec+=ave[w][m];
        }
        cout<<st<<" ";
    }
    cout<<tec<<endl;
    
    return 0;
}

Measured memory_bytes: 1196
#include <iostream>
#include <string>
#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;

int main() {
	int x, y;
	cin >> x >> y;
	if (x + y >= 10)cout << "error\n";
	else {
		cout << x + y << "\n";
	}

	return 0;
}

Measured memory_bytes: 256
import std.stdio,std.string,std.conv;

int main()
{
	string s;
	bool[int] m;
	bool[int] m2;
	int[int] count;


	while((s = readln.chomp).length != 0)
	{
		string[] _s = s.split(",");
		int a = _s[0].to!int;
		m[a] = true;
		count[a]++;
	}

	while((s = readln.chomp).length != 0)
	{
		string[] _s = s.split(",");
		int a = _s[0].to!int;
		m2[a] = true;
		count[a]++;
	}

	foreach(i;0..1001)
	{
		bool* p = (i in m);
		bool* p2 = (i in m2);
		if(p && p2)
		{
			writeln(i," ",count[i]);
		}
	}

	return 0;
}

Measured memory_bytes: 1064
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>

//#define PI 3.141592653589

using namespace std;



int main()
{
	int pasta[3];
	int juice[2];
	
	for (int i=0; i<3; i++) cin >> pasta[i];
	for (int i=0; i<2; i++) cin >> juice[i];
	sort(pasta, pasta+3);
	sort(juice, juice+2);
	
	cout << pasta[0] + juice[0] - 50 << endl;
	
	//for (int i=0; i<3; i++) cout << pasta[i] << endl;
	
	return 0;
}

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

int main(){
    constexpr long MOD = 1000000007;
    long N;
    cin >> N;
    long dp{N};
    vector<long> sum(4, (N - 1) * N % MOD);
    sum[0] = 0;
    for(long i = 3; i != N + 3; ++i){
        sum[3] = sum[2] - 1 + ((dp += sum[0]) %= MOD);
        rotate(sum.begin(), sum.begin() + 1, sum.end());
    }
    cout << dp << endl;
    return 0;
}

Measured memory_bytes: 256
import numpy as np
A,B,M = map(int,input().rstrip().split())
a = list(map(int,input().rstrip().split()))
b = list(map(int,input().rstrip().split()))

minp = min(a) + min(b)

minpp = 10**6
for k in range(M):
  i,j,c = map(int,input().rstrip().split())
  minpp = min(a[i-1]+b[j-1]-c,minpp)

print(min(minp,minpp))

Measured memory_bytes: 27492
#include<bits/stdc++.h>
 
 
using namespace std;
 
 
 
int main() {
 
  int R;
  cin >> R;
  if(R<1200)cout << "ABC" << endl;
  else if(R < 2800)cout << "ARC" << endl;
  else cout << "AGC" << endl;
  return 0;
 
 
}

Measured memory_bytes: 256
e[124][101],v[101],x,l;W(a,i,b){++l>x?x=l:0;for(i=v[a]=1;b=e[a][i++];)v[b]||W(b);v[a]=!l--;}main(m,a,b){for(;scanf("%d",&m)*m;x=!printf("%d\n",x)){for(bzero(e,5e4);m--;e[e[a][++*e[a]]=b][++*e[b]]=a)scanf("%d%d",&a,&b);for(a=101;--a;)v[a]||W(a);}}

Measured memory_bytes: 460
#include<cstdio>
#include<algorithm>
using namespace std;

int main(){
    int A,B,K,tmp;
    scanf("%d%d%d",&A,&B,&K);
    for(int i=A;i<=A+K-1;i++)
        if(i>=A&&i<=B)
            printf("%d\n",tmp=i);
    for(int i=max(tmp+1,B-K+1);i<=B;i++)
        printf("%d\n",i);
}
/**/

Measured memory_bytes: 128
#include<iostream>
#include <list>
#include<stack>
#include<queue>
#include <vector>
#include <set>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
#include<string>
#include <functional>
#include<fstream>

#define FOR(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define REP(i,n) FOR((i),0,(n))
#define LL long long
#define CLR(a) memset((a),0,sizeof(a))
#define SZ(x) (int((x).size()))
#define WAITING(str) int str;std::cin>>str;
#define DEBUGING(str) cout<<str<<endl
using namespace std;

const LL MOD = 1000000007;// 10^9+7
const int INF = (1 << 30);


//変数
int N, K, start;






//サブ関数
//入力
void input()
{
	cin >> N >> K;
	int tmp;
	REP(i, N) {
		cin >> tmp;
		if (tmp == 1)start = i;
	}
}


//計算
void calc()
{
	if (N == K)cout << 1 << endl;
	else cout << int(ceil(1.*(N - 1) / (K - 1))) << endl;

}


//出力
void output()
{

}


//デバッグ
void debug()
{
	int N;
	cin>>N;
}


//メイン関数
int main()
{
	input();
	calc();
	output();
	debug();
	
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define endl "\n"
#define F first
#define S second
#define def(x) cerr << #x << " is " << x << endl;
#define mod 1000000007
#define pb push_back
#define FOR(i,a,n) for(ll i=a;i<n;i++)
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define all(a) a.begin(),a.end()
const int NUM = 2e5 + 5;
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << endl;
    err(++it, args...);
}

int main(){
    ios
    int num_tests=1; 
    //cin>>num_tests;
    while(num_tests-->0){
        string s; cin>>s;
        int q; cin>>q;
        bool cur = false;
        string front,back;
        while(q--){
            int t; cin >> t;
            if(t==1) cur = !cur;
            else{
                int where; cin >> where;
                char what; cin >> what;
                if(where==1 && !cur || where==2 && cur){
                    front.pb(what);
                }
                else back.pb(what);
            }
        }
        if(cur){
            reverse(all(back));
            cout<<back;
            reverse(all(s));
            cout<<s;
            cout<<front;
        }
        else{
            reverse(all(front));
            cout<<front<<s<<back;

        }
    }   
}


Measured memory_bytes: 3904
// Author : Sarthak Kapoor
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int ll
#define rep(i,n) for(int i=0;i<n;++i)
#define repa(i,a,n) for(int i=a;i<n;++i)
#define repr(i,n) for(int i=n-1;i>=0;--i)
#define repba(i,b,a) for(int i=b;i>=a;--i)
#define repab(i,a,b) for(int i=a;i<b;++i)
#define ll long long
#define pi pair<int,int> 
#define pii pair<pi,int>
#define ull unsigned long long
#define vi vector<int>
#define viip vector<pair<int,pair<int,int> > > 
#define mp make_pair
#define vip vector<pair<int,int> >
#define pb push_back 
#define fi first
#define sec second
#define all(v) v.begin(),v.end()
#define s(v) v.size()
ll mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());//use rng()%n for numbers in range [0,n-1]
ll gcd(ll a,ll b){
	if(b==0)return a;
	return gcd(b,a%b);
}
ll fastexp(ll x,ll a){
    ll res = 1;
    while(a>0){
        if(a&1){
            res = (res*x)%mod;
        }
        a=a>>1;
        x=(x*x)%mod;
    }
    return res;
}
ll inverse(ll n){
    return fastexp(n,mod-2);
}
template <typename T>
void add(T &a, T b){
	a += b;
	if(a >= mod)a -= mod;
}
template <typename T>
void sub(T &a, T b){
	a -= b;
	if(a < 0)a += mod;
}
template <typename T>
void mul(T &a, T b){
	a *= b;
	if(a >= mod)a %= mod;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,k;
	cin>>n>>k;
	vip v(n);
	int z = 0;
	int c = 0;
	int f = 0;
	rep(i,n){
		cin>>v[i].fi;
		if(v[i].fi == 0)z++;
		if(v[i].fi > 0){
			f = 1;
			c = -1;
		}
		else if(v[i].fi == 0){
			f = 0;
		}
		else{
			f = -1;
		}
		v[i].fi = abs(v[i].fi);
		v[i].sec = f;
	}
	if(c == 0 && k%2 == 1){
		sort(all(v));
		int ans = 1;
		rep(i,k){
			mul(ans,v[i].fi);
			// cout<<v[i].fi<<" " ;
		}
		ans *= -1;
		ans += mod;
		if(ans >= mod)ans -= mod;
		cout<<ans;
		return 0;
	}
	if(n == k){
		int ans = 1 ;
		int g = 0;
		rep(i,n){
			mul(ans,v[i].fi);
			if(v[i].sec == -1)g++;
		}
		if(g%2){
			ans *= -1;
			ans += mod;
		}
		cout<<ans;
		return 0;
	}
	sort(all(v),greater<pi>());
	int p = 0;
	int ans = 1;
	rep(i,k){
		if(v[i].sec < 0)p++;
		mul(ans,v[i].fi);
	}
	if(p % 2 == 0){
		cout<<ans;
		return 0;
	}
	set<int> s[2];
	repa(i,k,s(v)){
		if(v[i].sec < 0)s[0].insert(v[i].fi);
		else if(v[i].sec > 0)s[1].insert(v[i].fi);
	}
	int smallestneg;
	int smallestpos = -1;
	rep(i,k){
		if(v[i].sec < 0){
			smallestneg = v[i].fi;
		}
		else if(v[i].sec > 0){
			smallestpos = v[i].fi;
		}
	}	
	int changepos = -1;
	int changeneg = -1;
	if(smallestpos != -1 && s(s[0]) > 0){
		changepos = *s[0].rbegin();
	}
	if(s(s[1]) > 0){
		changeneg = *s[1].rbegin();
	}
	if(changepos == -1){
		mul(ans,changeneg);
		mul(ans,inverse(smallestneg));
	}
	else if(changepos == -1 && changeneg == -1){
		ans = 0;
	}
	else if(changeneg*smallestpos > changepos*smallestneg){
		mul(ans,changeneg);
		mul(ans,inverse(smallestneg));
	}
	else{
		mul(ans,changepos);
		mul(ans,inverse(smallestpos));	
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 7300
#include<iostream>
#include<cstdlib>

#include<cmath>
#include<map>
#include<string>
#include<vector>
#include<algorithm> 

using namespace std;

# define p(s) std::cout << s << endl;
# define printIf(j,s1,s2) std::cout << (j ? s1 : s2) << endl;
# define YES(j) std::cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
# define rep(n,i) for(i = 0 ; i < n ; i++)

int main()
{
    int n,m,c;cin >> n >> m;

    int r[52]={};

    for(int i = 0 ; i < m ; i ++){
        int a,b;cin >> a >> b;

        r[a]++;
        r[b]++;
    }

    for(int i = 1 ; i <= n ; i ++){
        cout << r[i] << endl;
    }
}

Measured memory_bytes: 256
//abc074_a.cpp
//Sat Sep  1 20:30:16 2018

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

int main(){
	int n,a;
	cin >> n >> a;

	cout << n*n-a << endl;
//	printf("%.4f\n",ans);
}

Measured memory_bytes: 764
#include<algorithm>
#include<iostream>
#include<set>
#include<vector>

#pragma GCC optimize("Ofast")

struct Roadwork{
  int x;
  int s;
  int t;
};

bool operator<(const Roadwork& rw1, const Roadwork& rw2){
  return rw1.x < rw2.x;
}

int main(){
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);
  
  int N, Q;
  std::cin >> N >> Q;
  
  std::vector<Roadwork> rw(N);
  
  for(int i = 0; i < N; i++){
    std::cin >> rw.at(i).s >> rw.at(i).t >> rw.at(i).x;
  }
  
  std::sort(rw.begin(), rw.end());
  
  std::set<int> D;
  std::vector<std::pair<int, int>> destination;
  
  for(int i = 0; i < Q; i++){
    int d;
    std::cin >> d;
    
    D.insert(d);
  }
  
  for(int i = 0; i < N; i++){
    std::set<int>::iterator b, t;
    b = D.lower_bound(rw.at(i).s - rw.at(i).x);
    t = D.lower_bound(rw.at(i).t - rw.at(i).x);
    
    for(std::set<int>::iterator j = b; j != t; j++){
      
      destination.emplace_back(std::make_pair(*j, rw.at(i).x));
    }
    D.erase(b, t);
  }
  
  for(std::set<int>::iterator j = D.begin(); j != D.end(); j++){
    destination.emplace_back(std::make_pair(*j, -1));
  }
  
  std::sort(destination.begin(), destination.end());
  
  for(int i = 0; i < Q; i++){
    std::cout << destination.at(i).second << '\n';
  }
  
  return 0;
}


Measured memory_bytes: 15344
#include<iostream>
using namespace std;
#define ll long long
const ll mod=1e9+7;
ll qm(ll a,ll b){
    ll res=1;
    while(b>0){
        if(b&1)res=res*a%mod;b>>=1;a=a*a%mod;
    }
    return res;
}
ll fac[500000];
ll inv[500000];
void init(){
    fac[0]=fac[1]=inv[0]=inv[1]=1;
    for(int i=2;i<500000;++i)fac[i]=fac[i-1]*i%mod;
    inv[499999]=qm(fac[499999],mod-2);
    for(int i=499998;i>1;--i){
        inv[i]=inv[i+1]*(i+1)%mod;
    }
}
ll C(int n,int m){
    if(m==0||n==m)return 1;
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main()
{
	init();
	int n,m,a,b;
	cin>>n>>m>>a>>b;
	ll ans=C(n-1+m-1,n-1);
	for(int i=1;i<=b;++i){
        ll ty=C(abs(n-a-1)+abs(1-i),abs(n-a-1));
        ll tu=C(abs(1-a)+abs(m-i),abs(1-a));
        ty=ty*tu%mod;
        ans-=ty;
        ans=(ans%mod+mod)%mod;
	}
	 cout<<ans<<endl;
	return 0;
}


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

signed main(){
  int N,num=0;
  cin>>N;
  vector<int> A(N);
  string ans="Yes";
  rep(i,N)cin>>A[i];
  int M=A[0];
  rep(i,N){
    if(A[i]>M){
      M=A[i]-1;
    }
    if(A[i]<M){
      ans="No";
      break;
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 1024
import sys
N,M=map(int,input().split())
A=[0]*N
B=[0]*N
for i in range(0,N):
  A[i],B[i]=map(int,input().split())
index=sorted(range(len(A)), key=lambda k: A[k])
cost=0
get=0
for i in index:
  if get+B[i]<M:
    get += B[i]
    cost += A[i]*B[i]
  else:
    cost += A[i]*(M-get)
    print(cost)
    sys.exit()

Measured memory_bytes: 16540
N = int(input())
words = []
for _ in range(N):
    words.append(input())

if (len(words)==len(set(words))):
    for i in range(N-1):
        if(words[i][-1] != words[i+1][0]):
            status = 'error'
            break
        elif(i == N-2):
            status = 'done'
else:
    status = 'error'

if(status == 'done'):
    print('Yes')
elif(status == 'error'):
    print('No')


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll n,m;
    cin>>n>>m;
    ll x[n],y[m];
    for(int i=0;i<n;i++)cin>>x[i];
    for(int i=0;i<m;i++)cin>>y[i];
    ll ans=0;
    sort(x,x+n);
    sort(y,y+m);
    ll num=0;
    for(ll i=0LL;i<n;i++){
        num+=x[i]*i;
        num-=x[i]*(n-i-1);
        num%=mod;
    }
    for(int i=0;i<m;i++){
        ans+=y[i]*i;
        ans-=y[i]*(m-i-1);
        ans%=mod;
    }
    ans*=num;
    ans%=mod;
    ans+=mod;
    ans%=mod;
    cout << ans<<endl;
    return 0;
}


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

typedef vector<int> vec;
typedef vector<vec> mat;

int main(){
    int P, Q;
    while(cin >> P >> Q, P|Q){
        mat A;
        
        string line;
        int r = 0, c = 0, s = 0;
        for(int i=0; i<P; i++){
            cin >> line;
            for(int i=0; i<line.size(); i++){
                if(line[i] != '.'){
                    A.push_back(vec({r, c, s, i}));
                    break;
                }
            }
            for(auto ch: line){
                if(ch == '(') r++;
                if(ch == ')') r--;
                if(ch == '{') c++;
                if(ch == '}') c--;
                if(ch == '[') s++;
                if(ch == ']') s--;
            }
        }
        
        r = 0, c = 0, s = 0;
        for(int i=0; i<Q; i++){
            cin >> line;
            
            int ans = -2;
            for(int R=1; R<=20; R++){
                for(int C=1; C<=20; C++){
                    for(int S=1; S<=20; S++){
                        bool is_valid = true;
                        for(auto v: A)
                            is_valid &= v[0]*R + v[1]*C + v[2]*S == v[3];
                        
                        if(is_valid){
                            if(ans == -2)
                                ans = r*R + c*C + s*S;
                            if(ans != r*R + c*C + s*S)
                                ans = -1;
                        }
                    }
                }
            }
            cout << ans << (i==Q-1? "\n": " ");
            
            for(auto ch: line){
                if(ch == '(') r++;
                if(ch == ')') r--;
                if(ch == '{') c++;
                if(ch == '}') c--;
                if(ch == '[') s++;
                if(ch == ']') s--;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 3136
fun main(args: Array<String>) {
    val (n, a, b) = readLine()!!.split(" ").map(String::toLong)

    if (b < a) {
        println(0)
        return
    }
    when (n) {
        1L -> {
            if (a != b) {
                println(0)
            } else {
                println(1)
            }
        }
        else -> {
            val c = n - 2
            var min = a * c
            var max = b * c
            println(max - min + 1)
        }
    }
}



Measured memory_bytes: 37620
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<n;++i)

using namespace std;

typedef pair<int,int>P;

const int MAX_N = 105;

int w[MAX_N];
int v[MAX_N];
int n,W;

int main()
{
	scanf("%d%d",&n,&W);
	rep(i,n){
		scanf("%d%d",&w[i],&v[i]);
	}
    vector<int> vec[4];
    rep(i,n){
        vec[w[i]-w[0]].push_back(v[i]);
    }
    rep(i,4){
        sort(vec[i].begin(),vec[i].end(),greater<int>());
    }
    int sm[4][MAX_N];
    rep(i,4){
        sm[i][0] = 0;
        rep(j,vec[i].size()){
            sm[i][j+1] = sm[i][j] + vec[i][j];
        }
    }
    int ans = 0;
    rep(i,vec[0].size()+1){
        rep(j,vec[1].size()+1){
            rep(k,vec[2].size()+1){
                rep(l,vec[3].size()+1){
                    ll wsum = (ll)w[0]*i + (ll)(w[0]+1)*j + (ll)(w[0]+2)*k + (ll)(w[0]+3)*l;
                    if(wsum <= W){
                        int vsum = sm[0][i] + sm[1][j] + sm[2][k] + sm[3][l];
                        if(vsum > ans){
                            ans = vsum;
                        }
                    }
                }
            }
        }
    }
    printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#define NDEBUG

// verified at https://judge.yosupo.jp/submission/3400
#ifndef Union_find_hpp
#define Union_find_hpp

#include <cassert>
#include <cstddef>
#include <vector>

class union_find
{
    std::vector<int> link;

public:
    explicit union_find(const size_t n) : link(n, -1) {}

    size_t find(size_t x)
    {
        assert(x < size());
        return link[x] < 0 ? x : (link[x] = find(link[x]));
    }

    size_t size() const { return link.size(); }

    size_t size(const size_t x)
    {
        assert(x < size());
        return -link[find(x)];
    }

    bool same(const size_t x, const size_t y)
    {
        assert(x < size() && y < size());
        return find(x) == find(y);
    }

    size_t unite(size_t x, size_t y)
    {
        assert(x < size() && y < size());
        if((x = find(x)) != (y = find(y)))
        {
            if(link[x] > link[y]) std::swap(x, y);
            link[x] += link[y];
            link[y] = x;
        }
        return x;
    }
}; // class union_find

#endif // Union_find_hpp

#include <algorithm>
#include <iostream>
#include <tuple>

using namespace std;

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

    int n,h,w; cin>>n>>h>>w;
    vector<tuple<int,int,int>> cards(n);
    for(auto &e : cards)
    {
        int r,c,a; cin>>r>>c>>a;
        --r,--c; c+=h;
        e=tie(a,r,c);
    }
    sort(cards.rbegin(),cards.rend());
    union_find uf(h+w);
    long long ans{};
    bool ext[2<<17]={};
    for(auto &e : cards)
    {
        int a,r,c; tie(a,r,c)=e;
        r=uf.find(r),c=uf.find(c);
        if(r!=c)
        {
            if(ext[r] and ext[c]) continue;
            ext[uf.unite(r,c)]=ext[r]||ext[c];
            ans+=a;
        }
        else if(!ext[r])
        {
            ext[r]=true;
            ans+=a;
        }
    }
    cout << ans << "\n";
}


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


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    map<string, int> a;
    map<string, int> b;
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        string s;
        cin >> s;
        a[s]++;
    }
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        string s;
        cin >> s;
        b[s]++;
    }
    int sol = 0;
    for (auto& p : a)
        sol = max(sol, p.second - b[p.first]);
    cout << sol;
}


Measured memory_bytes: 256
#include <algorithm>
#include <string.h>
#include <iostream>
#include <stdio.h>

using namespace std;

typedef long long ll;
ll x;
ll res = -1;

int main() {
	cin >> x;

	for (ll b = -1000; b <= 1000; b++) {
		ll t = b * b * b * b * b + x;

		ll l = b + 1, r = 1000;
		while (l < r) {
			ll mid = l + r >> 1;
			if (mid * mid * mid * mid * mid == t)
				res = mid;
			if (mid * mid * mid * mid * mid > t) r = mid;
			else l = mid + 1;
		}

		if (res != -1) {
			cout << res << " " << b << endl;
			return 0;
		}
	}

	return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef vector<double> Vec;
typedef vector<Vec> Mat;
typedef pair<ll,ll> P;
typedef pair<double,ll> Pd;
typedef priority_queue<P,vector<P>,greater<P>> P_queue;
typedef priority_queue<Pd,vector<Pd>,greater<Pd>> Pd_queue;

const ll MOD=998244353;
const ll mod=1000000007;
const ll INF=1e15;
const double DEL=1e-3;
vec dx={1,0,-1,0};
vec dy={0,1,0,-1};

#define REP(i,a,b) for(int i=(int)a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define mp make_pair
#define ALL(a) a.begin(),a.end()
#define SORT(a) sort(ALL(a))
#define U_ERASE(V) V.erase(unique(ALL(V)), V.end());
#define ADD(a,b) a=(a+b)%MOD
#define CHECK cout<<"arrived"<<endl

ll dp[45001];

ll ruijou(ll n, ll k){
    if(!k) return 1;
    ll a=ruijou(n,k/2);
    a=(a*a)%MOD;
    return k%2 ? (a*n)%MOD : a;
}



int main(){
    ll N; cin>>N;
    vec d(N);
    rep(i,N) cin>>d[i];
    ll SUM=0;
    rep(i,N) SUM+=d[i];
    dp[0]=1;
    ll ans=ruijou(3,N);
    ll A=(SUM+1)/2;
    //sort(ALL(d));
    //cout<<ans<<' '<<A<<endl;
    rep(i,N) for(int k=A-1; k>=0; k--){
        if(k+d[i]>=A){
            ll x=(dp[k]*ruijou(3,N-i))%MOD;
            ADD(ans,MOD-x);
        }
        else ADD(dp[k+d[i]],dp[k]);
        dp[k]=(2*dp[k])%MOD;
    }
    if(SUM%2==0){
        rep(i,45001) dp[i]=0;
        dp[0]=1;
        rep(i,N) for(int k=A-1; k>=0; k--){
            if(k+d[i]<A) ADD(dp[k+d[i]],dp[k]);
            else if(k+d[i]==A) ADD(ans,3*dp[k]);
        }
    }
    cout<<ans<<endl;

}

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

int N;
LLI dp[22][1<<21] = {};
int a[21][21] = {};

int main() {
	
	int i,j;
	int N;
	
	cin >> N;
	for( i=0; i<N; i++) {
		for( j=0; j<N; j++) {
			cin >> a[i][j];
		}
	}
	
	dp[0][0] = 1;
	for( i=0; i<N; i++) {
		for( j=0; j < N; j++) {
			if( !a[i][j])
				continue;
			for( int k=0; k<(1<<N); k++) {
				if( k&(1<<j) ) {
					dp[i+1][k] += dp[i][k^(1<<j)];
					dp[i+1][k] %= MOD;
				}
			}
		}
	}
	
	LLI ans = dp[N][(1<<N)-1];
	printf("%lld\n", ans);
	
	return 0;
}

Measured memory_bytes: 347800
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx")
//#undef LOCAL
#include <bits/stdc++.h>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;

#ifdef LOCAL
struct PrettyOS {
    ostream& os;
    bool first;
    template <class T> auto operator<<(T&& x) {
        if (!first) os << ", ";
        first = false;
        os << x;
        return *this;
    }
};
template <class... T> void dbg0(T&&... t) {
    (PrettyOS{cerr, true} << ... << t);
}
#define dbg(...)                                            \
    do {                                                    \
        cerr << __LINE__ << " : " << #__VA_ARGS__ << " = "; \
        dbg0(__VA_ARGS__);                                  \
        cerr << endl;                                       \
    } while (false);
#else
#define dbg(...)
#endif

template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    return os << "P(" << p.first << ", " << p.second << ")";
}

template <class T> ostream& operator<<(ostream& os, const V<T>& v) {
    os << "[";
    for (auto d : v) os << d << ", ";
    return os << "]";
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    using D = double;
    D PI = acos(D(-1));
    D a, b, x;
    cin >> a >> b >> x;

    D lw = 0, up = 90;
    for (int ph = 0; ph < 100; ph++) {
        D md = (lw + up) / 2;
        D md2 = md / 180 * PI; // 180 -> PI
        D z = 0;
        if (tan(md2) <= b / a) {
            z += a * a * a * tan(md2) / 2;
        } else {
            z += a * b * a;
            z -= b * b * tan(PI/2 - md2) * a / 2;
        }
        z = a * a * b - z;

        if (z > x) {
            lw = md;
        } else {
            up = md;
        }
    }
    cout << lw << endl;
    return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
#define int long long


using namespace std;

vector<int>mm[21];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int a,b;
    cin>>a>>b;
    if(a>2*b)
        cout<<a-2*b;
    else
        cout<<0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
#include<map>
#include<iostream>
#include<math.h>
#define ll long long
#define ld long double
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;


int main(){
    int N;
    int a = 0;int b = 0; int c = 0; int d = 0;
    string s;
    cin >> N;
    for(int i = 0; i < N;i++){
        cin >> s;
        if(s == "AC") a++;
        else if(s == "WA") b++;
        else if(s == "TLE") c++;
        else d++;
    }
    cout << "AC x" << " " << a << endl;
    cout << "WA x" << " " << b << endl;
    cout << "TLE x" << " " << c << endl;
    cout << "RE x" << " " << d << endl;
}

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

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define a first
#define b second
#define sz size()
#define pb(x) push_back(x) 
#define bg begin()
#define ed end()
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define mp(x,y) make_pair(x,y)
const ll MOD=1000000007;

ll maxx(ll x,ll y,ll z){
	return max(max(x,y),z);
}
ll minn(ll x,ll y,ll z){
	return min(min(x,y),z);
}
ll gcd(ll x,ll y){
	if(x%y==0) return y;
    else return gcd(y,x%y);
}
ll lcm(ll x,ll y){
	return x*(y/gcd(x,y));
}
ll myceil(ll x,ll y){//yがいくつ集まったらx以上になるか
	if(x<=y) return 1;
	else if(x%y==0) return x/y;
	else return x/y+1;
}

//a,b x
int main(){
	ll N; cin>>N;
	if(N<1200) cout<<"ABC";
	else cout<<"ARC";
}

Measured memory_bytes: 768
use std::io::*;
use std::collections::BTreeSet;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn abc(t: f32, a: f32, h: Vec<f32>) -> usize {
    let mut res = 0;
    let mut min_gap = 10000.0;
    for (i, h_) in h.iter().enumerate() {
        let mut tmp = t - h_ * 0.006;
        let mut gap = (a - tmp).abs();
        if gap < min_gap {
            min_gap = gap;
            res = i+1;
        }
    }
    return res
}

fn main() {
    /*
    assert_eq!(abc(), "Yes");
    assert_eq!(abc(101), "No");
    assert_eq!(abc(999999999), "Yes");
    */
    input!{
        n: usize,
        t: f32,
        a: f32,
        h: [f32; n],
    }
    let result = abc(t, a, h);
    println!("{}", result)
}



Measured memory_bytes: 4352
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        int j = partition(a, 0, a.length - 1);
        for (int i = 0; i < n; i++) {
            if (i == j) {
                System.out.print("[");
            }
            System.out.print(a[i]);
            if (i == j) {
                System.out.print("]");
            }
            if (i == a.length - 1) {
                System.out.println("");
            } else {
                System.out.print(" ");
            }
        }
    }

    private static int partition(int[] a, int p, int r) {
        int x = a[r];
        int i = p - 1;
        for (int j = p; j < r; j++) {
            if (a[j] <= x) {
                i++;
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
        i++;
        int t = a[i];
        a[i] = a[r];
        a[r] = t;
        return i;
    }
}

Measured memory_bytes: 72548
n, k = [int(a) for a in input().split()]
v = [int(a) for a in input().split()]


def value(left, right):
    l_popped = v[:left]
    r_popped = v[-right:] if right > 0 else []
    popped = l_popped + r_popped

    negative = [x for x in popped if x < 0]
    negative.sort()
    
    rest = k - (left + right)
    pushed = negative[:rest]

    return sum(popped) - sum(pushed)


cap = min(n, k)
result = max(
    value(left, right)
    for left in range(k + 1)
    for right in range(cap - left + 1)
)

print(result)



Measured memory_bytes: 3064
require 'set'; require 'prime'; require 'pp'
INF=Float::INFINITY; MOD=10**9+7
x = gets.chomp.to_i

-500.upto(500) do |a|
  -500.upto(500) do |b|
    if (a**5) - (b**5) == x
      puts [a,b].join(' ')
      exit
    end
  end
end






Measured memory_bytes: 14744
#include<iostream>
#include<string>

using namespace std;

char str[102][102], c;
int H, W;

int main(){

	cin >> H >> W;
	for(int l = 0; l < H+2; l++){
		for(int m = 0; m < W+2; m++){
			if(l == 0 || l == H+1 || m == 0 || m == W+1){
				str[m][l] = '#';
			}else{
				cin >> c;
				str[m][l] = c;
			}
		}
	}

	for(int l = 0; l < H+2; l++){
		for(int m = 0; m < W+2; m++){
			cout << str[m][l];
		}
		cout << endl;
	}
	return 0;
}


Measured memory_bytes: 256