akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long LL;
typedef long double ld;
typedef vector<ll>VI;
typedef pair<ll,ll>P;
#define VV(T) vector<vector<T>>
#define sz(x) int(x.size())
#define PI 3.1415926535897932384626433832795
#define rep(i, n) for (ll i = 0; i < (ll)n; i++)
#define reprev(i,n) for (ll i=(ll)n-1;i>=0;i--)
#define ALL(a)  (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
#define c_max(a, b) (((ll)a)>((ll)b)?(a):(b))
#define c_min(a,b) (((ll)a)<((ll)b)?(a):(b))
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; }
#define vmax(v) *max_element(ALL(v))
#define vmin(v) *min_element(ALL(v))
#define $(x) {cout<<#x<<" = " <<(x)<<endl;}
#define fi first
#define se second
#define MAX 100100//5
#define MAX2 200100
#define MAX6 1001001//6
#define MAX7 10010010//7
#define SENTINEL 2000000000//9
#define INF 1<<30
#define INFTY 1LL<<61
#define MAX_INT INT_MAX
#define Endl '\n'
#define CLR(mat) memset(mat, 0, sizeof(mat))
inline ll GCD(ll a,ll b){return b?GCD(b,a%b):a;}//最大公約数
inline ll lcm(ll a,ll b){return a*b/GCD(a,b);}//最小公倍数
template<class T> bool contain(const std::string& s, const T& v) {
   return s.find(v) != std::string::npos;
}
const int MOD = 1000000007;
//const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
// vector型から重複を削除 list.erase(unique(ALL(list)),list.end());
// g++ -o a a.cpp -Wall -lm -std=c++17
//push_back -> emplace_back
ll dp[MAX][3];
ll abc[3][MAX];
int main(){
   ll n;cin>>n;
   rep(j,n)rep(i,3)cin>>abc[i][j];
   CLR(dp);
   rep(i,n){
      dp[i+1][0]=max(dp[i][1]+abc[0][i],max(dp[i][2]+abc[0][i],dp[i+1][0]));
      dp[i+1][1]=max(dp[i][2]+abc[1][i],max(dp[i][0]+abc[1][i],dp[i+1][1]));
      dp[i+1][2]=max(dp[i][0]+abc[2][i],max(dp[i][1]+abc[2][i],dp[i+1][2]));
   }
   ll ans=0;
   rep(i,3)chmax(ans,dp[n][i]);
   cout<<ans<<endl;
}

Measured memory_bytes: 8208
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define test() ull t;cin>>t;while(t--)
#define pb push_back
#define mkp make_pair
#define nl cout<<endl
#define MOD 1000000007
#define loop(i,start,end) for(ll i=start;i<end;i++)
#define N 100001
#define all(v) v.begin(),v.end()
#define oa(a,n) for(int i=0;i<n;i++)cout<<a[i]<<" ";nl
#define ov(a) for(int i=0;i<a.size();i++)cout<<a[i]<<" ";nl
int main() 
{
    fastio();

    int n,w;
    cin>>n>>w;
    vector<ll>a(n+1),v(n+1);
    for(int i =0;i<n;i++)cin>>a[i+1]>>v[i+1];

    ll dp[w+1][n+1];
	memset(dp,0,sizeof(dp));
    for(int i = 0;i<=w;i++)
    {
    	for(int j = 1;j<=n;j++)
    	{
    		if(a[j]>i)dp[i][j] = dp[i][j-1];
    		else
    			dp[i][j] = max(dp[i][j-1],dp[i-a[j]][j-1]+v[j]);
    	}
    }

    cout<<dp[w][n]<<endl;


	return 0;
}

Measured memory_bytes: 79232
n,m = map(int,input().split())
dp = [float('inf') for i in range(2 ** n)]
dp[0] = 0

keys = []
for i in range(m):
  a,b = map(int,input().split())
  cs = list(map(int,input().split()))
  key = 0
  for c in cs:
    key += 2 **(c-1)
  dp[key] = a
  keys.append((key,a))
keys.sort()


for i in range(2**n):
  for key,a in keys:
    if dp[i|key] > dp[i] + a:
      dp[i|key] = dp[i] + a
print(dp[-1] if dp[-1] != float('inf') else -1)

Measured memory_bytes: 3316
import Control.Monad
import Control.Applicative
import Data.Maybe
import qualified Data.ByteString.Char8 as B

data Tree = E | T Int Tree Tree
inf = 2^31-1
n_ = 2^17

root = T inf root root

val (T x _ _) = x
val E = inf

update (T _ left right) k x l r
    | r - l == 1 = T x E E
    | k < mid =
        let newleft = update left k x l mid
        in T (min (val newleft) (val right)) newleft right
    | otherwise =
        let newright = update right k x mid r
        in T (min (val left) (val newright)) left newright
    where mid = (l + r) `div` 2

query (T val left right) a b l r
    | b <= l || r <= a = inf
    | a <= l && r <= b = val
    | otherwise = min (query left a b l mid) (query right a b mid r)
    where mid = (l + r) `div` 2

solve [] _ = []
solve ([t,x,y]:qs) tree = case t of
    0 -> solve qs (update tree x y 0 n_)
    1 -> (query tree x (y + 1) 0 n_):(solve qs tree)

main = do
    _ <- getLine
    qs <- map (map (fst . fromJust . B.readInt) . B.words) . B.lines <$> B.getContents
    mapM_ print $ solve qs root


Measured memory_bytes: 51244
#include <bits/stdc++.h> // Tomasz Nowak
using namespace std;     // XIII LO Szczecin
using L = long long;

#define FOR(i, l, r) for(int i = l; i <= r; ++i)
#define REP(i, n) FOR(i, 0, n - 1)
#define FORD(i, l, r) for(int i = r; i >= l; --i)
#define REPD(i, n) FORD(i, 0, n - 1)
constexpr int inf = 0x3f3f3f3f;
template<class T> int size(T &x) {
	return int(x.size());
}

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

	int h, w;
	constexpr int mod = int(1e9) + 7;
	cin >> h >> w;
	vector<vector<int>> dp(w, vector<int>(h)), blocked = dp;
	dp[w - 1][h - 1] = 1;
	REP(y, h)
		REP(x, w) {
			char c;
			cin >> c;
			blocked[x][y] = c == '#';
		}
	REPD(x, w)
		REPD(y, h) {
			if(blocked[x][y])
				continue;
			if(x + 1 < w)
				dp[x][y] += dp[x + 1][y];
			if(y + 1 < h)
				dp[x][y] += dp[x][y + 1];
			dp[x][y] %= mod;
		}
	cout << dp[0][0] << '\n';
}



Measured memory_bytes: 8192
//agrawal117
//chahatagrawal117
#include<bits/stdc++.h>
#define endl '\n'
#define mod 1000000007
typedef long long int ll;
using namespace std;
#define MAX 300005
vector<ll> v[MAX];
ll in[MAX];
ll out[MAX];
ll dp[MAX];
ll n;
void dfs(int node, int par)
{
    dp[node]=1;
    in[node]=1LL;
    for(auto i: v[node]){
        if(i^par)
        {
            dfs(i,node);
            dp[node]+=dp[i];
            dp[node]%=mod;
            in[node]=(in[node]*in[i])%mod;
        }
    }
    dp[node]%=mod;
    in[node]=(in[node]*dp[node])%mod;
}
ll power(ll a, ll b)
{
    a%=mod;
    ll res=1LL;
    while(b>0)
    {
        if(b&1LL) res=(res*a)%mod;
        b>>=1;
        a=(a*a)%mod;
    }
    return res%mod;
    
}
ll inv(ll a)
{
    return power(a,mod-2)%mod;
}
void bfs(int node, int par)
{
    ll mult=1LL;
    for(auto i: v[node]){
        if(i^par) mult=(mult*in[i])%mod;
    }
    for(auto i: v[node]) 
    {
        if(i^par)
        {
            ll sub=n-dp[i];
            out[i]=(((sub*out[node])%mod)*mult)%mod;
            out[i]=(out[i]*inv(in[i]))%mod;
            bfs(i,node);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
     cin>>n;
    for(int i=1;i<=n-1;i++){
        ll a, b; cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);    
    }
    dfs(1,1);
    out[1]=1LL;
    bfs(1,1);
    ll ans=0;
    ll fact=1;
    for(int i=1;i<=n;i++)fact=(fact*i)%mod;
    for(int i=1;i<=n;i++){
        ll val=in[i];
        val=(val*inv(dp[i]))%mod;
        val=(val*n)%mod;
        val=(val*out[i])%mod;
        ll f=inv(val);
        f=(fact*f)%mod;
        cout<<f<<endl;
        ans=(ans+f)%mod;
    }
    // cout<<an`s<<endl;
}





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

int main(){
  int N;
  cin >> N;
  if(N <= 104) cout << 0 << endl;
  else if(N <= 134) cout << 1 << endl;
  else if(N <= 164) cout << 2 << endl;
  else if(N <= 188) cout << 3 << endl;
  else if(N <= 194) cout << 4 << endl;
  else cout << 5 << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
void trace(int A[],int N){
  int i;
  for(i=0;i<N;++i) cout<<A[i]<<(i==N-1?"\n":" ");
}
void insertionSort(int A[],int N){
  int i,j,v;
  for(i=1;i<N;++i){
    v=A[i];
    j=i-1;
    while(j>=0&&A[j]>v){
      A[j+1]=A[j];
      j--;
    }
    A[j+1]=v;
    trace(A,N);
  }
}
int main(){
  int n,i;
  int a[101];
  cin>>n;
  for(i=0;i<n;++i) cin>>a[i];
  trace(a,n);
  insertionSort(a,n);
  return 0;
}

Measured memory_bytes: 3104
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>


using namespace std;
#define ll long long

ll S(ll n){
	ll m = n;
	ll sum = 0;
	while(m > 0){
		sum += m % 10;
		m /= 10;
	}
	return sum;
}

double calc(ll x){
	return 1.0 * x / S(x);
}

int main(void) {
	ll K;
	cin >> K;
	ll N = 1;

	while(K > 0){
		ll next = N;
		if(N < 9){
			next = N + 1;
		}else{
			ll min = 1e+15;
			for(int d = 0; d < log(N)/log(10)+1; d++){
				if(calc((ll)pow(10, d + 1) * ceil(N / pow(10, d + 1) + 1) - 1) < calc(min))
					min = (ll)pow(10, d + 1) * ceil(N / pow(10, d + 1) + 1) - 1;
			}
			next = min;
		}
		cout << N << endl;
		N = next;
		K--;
	}

	return 0;
}

Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;
#define Rep(i, n) for (int i = 0; i < (int)(n); i++)
#define BitRep(i, n) for (int i = 0; i < (int)(1 << n); i++)
#define Sum(vec) accumulate(vec.begin(), vec.end(), 0)
#define Sort(vec) sort(vec.begin(), vec.end())
#define Reverse(vec) reverse(vec.begin(), vec.end())

int main() {
	int K;
	string S;
	cin >> K >> S;
	if (S.size() <= K) {
		cout << S << endl;
	}
	else {
		cout << S.substr(0, K) << "..." << endl;
	}
	return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string str;
    cin>>str;
    bool temp=false;
    bool temp2=false;
    if(str[2]=='0')
    {
        if(str[3]>='1'&&str[3]<='9')
        {
            temp=true;
        }
    }
    else if(str[2]=='1')
    {
        if(str[3]>='0'&&str[3]<='2')
        {
            temp=true;
        }
    }
    if(str[0]=='0')
    {
        if(str[1]>='1'&&str[1]<='9')
        {
            temp2=true;
        }
    }
    else if(str[0]=='1')
    {
        if(str[1]>='0'&&str[1]<='2')
        {
            temp2=true;
        }
    }
    if(temp&&temp2)
    {
        cout<<"AMBIGUOUS\n";
    }
    else if(temp)
    {
        cout<<"YYMM\n";
    }
    else if(temp2)
    {
        cout<<"MMYY\n";
    }
    else
    {
        cout<<"NA\n";
    }
    return 0;
}

Measured memory_bytes: 3560
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

#define FOR(i, N) for (int i = 0; i < (int)N; i++)
#define FORIN(i, a, b) for (int i = a; i < (int)b; i++)
#define ALL(x) (x).begin(), (x).end()
#define MOD 1000000007
#define DEBUG(...) debug(__LINE__, ":" __VA_ARGS__)

using Pi = pair<int, int>;
using ll = long long;
const int INF = 1 << 28;

string to_string(string s) { return s; }

template <class S, class T>
string to_string(pair<S, T> p) {
  return "{" + to_string(p.first) + "," + to_string(p.second) + "}";
}

template <class T>
string to_string(unordered_set<T> s) {
  string ret = "{";
  for (T t : s) ret += to_string(t) + ",";
  ret += "}";
  return ret;
}

template <class T>
string to_string(vector<T> v) {
  string ret = "{";
  for (int i = 0; i < (int)v.size() - 1; ++i) {
    ret += to_string(v[i]) + ",";
  }
  if (v.size() > 0) {
    ret += to_string(v.back());
  }
  ret += "}";
  return ret;
}

void debug() { cerr << endl; }

template <class Head, class... Tail>
void debug(Head head, Tail... tail) {
  cerr << to_string(head) << " ";
  debug(tail...);
}

void print() { cout << endl; }

template <class Head, class... Tail>
void print(Head head, Tail... tail) {
  cout << to_string(head);
  print(tail...);
}

int D[13], ans[24], fin = 0;

void dfs(int i) {
  if (i == 13) {
    int last = 1, mind = INF;
    FORIN(j, 1, 25) {
      if (ans[j % 24]) {
        mind = min(mind, last);
        last = 1;
      } else {
        last++;
      }
    }
    fin = max(fin, mind);
  } else {
    if (D[i] == 1) {
      ans[i] = 1;
      dfs(i + 1);
      ans[i] = 0;
      ans[24 - i] = 1;
      dfs(i + 1);
      ans[24 - i] = 0;
    } else if (D[i] == 2) {
      ans[i] = 1;
      ans[24 - i] = 1;
      dfs(i + 1);
      ans[24 - i] = 0;
      ans[i] = 0;
    } else {
      dfs(i + 1);
    }
  }
}

int main() {
  int N;
  cin >> N;
  FOR(i, N) {
    int d;
    cin >> d;
    D[d]++;
    if (d == 0 || D[12] > 1 || D[d] > 2) {
      print(0);
      return 0;
    }
  }
  ans[0] = 1;
  dfs(1);
  print(fin);
  return 0;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] x = new int[N];
        for (int i = 0; i < x.length; ++i) {
            x[i] = sc.nextInt();
        }

        System.out.println(solve(x, K));

        sc.close();
    }

    static int solve(int[] x, int K) {
        return 2 * Arrays.stream(x).map(xi -> Math.min(xi, K - xi)).sum();
    }
}

Measured memory_bytes: 27600
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<complex>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using Complex = complex<double>;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1145141919810364364LL;
double PI = acos(-1.0);
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)



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

	ll k, q;
	cin >> k >> q;
	vector<ll>d(k);
	for (int i = 0; i < k; i++)cin >> d[i];
	for (int i = 0; i < q; i++) {
		ll ans = 0;
		vector<ll>d_(k),cnt(k);
		ll n, x, m;
		cin >> n >> x >> m;
		for (int j = 0; j < k; j++)d_[j] = d[j] % m;
		ll last = x;
		for (int j = 0; j < k; j++)cnt[j] = (n - j + k - 2) / k;
		for (int j = 0; j < k; j++) {
			last += d_[j] * cnt[j];
			if (d_[j] == 0)ans += cnt[j];
		}
		ans += (last / m) - (x / m);
		ans = (n-1) - ans;
		puts(ans);
	}

	return 0;
}


Measured memory_bytes: 384
A,B,M=map(int,input().split())

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

x=[0]*M
y=[0]*M
c=[0]*M

for i in range(M):
    x[i],y[i],c[i]=map(int,input().split())
    
cal_1=min(a)+min(b)
cal_2=[0]*M

for i in range(M):
    cal_2[i]=a[x[i]-1]+b[y[i]-1]-c[i]
    
cal_3=min(cal_2)

if cal_1>=cal_3:
    print(cal_3)
else:
    print(cal_1)

Measured memory_bytes: 27308
s = input()
n = len(s)

# 全体が回文かどうか
if s != s[::-1]:
    print('No')
# 1文字目から(N-1)/2文字目までからなる文字列が回文かどうか
elif s[:(n-1)//2] != s[:(n-1)//2][::-1]:
    print('No')
# Sの(N+3)/2文字目からN文字目までからなる文字列が回文かどうか
elif s[(n+3)//2-1:] != s[(n+3)//2-1:][::-1]:
    print('No')
else:
    print('Yes')

Measured memory_bytes: 9080
k=int(input())

if k%2==0 or k%5==0:
  print(-1)
  exit()

if k%7==0:
  l=9*k//7
else:
  l=9*k

ans=1
q=10%l

while q!=1:
  q*=10
  q%=l
  ans+=1

print(ans)

Measured memory_bytes: 9104
import { readFileSync } from "fs";

const read = () =>
  readFileSync(0, "utf8")
    .split("\n")
    .map((line) => line.split(" "));

const main = (input: string[][]) => {
  const [a, b] = input[0].map(Number);

  return b < a ? a - 1 : a;
};

console.log(main(read()));


Measured memory_bytes: 29644
#include <bits/stdc++.h>
#include <typeinfo>
#include <cxxabi.h>
#ifdef LOCAL
  #include "dbgtoki.hpp"
  #define DUMP(i) dump((string)TOSTRING(i), demangle(typeid(i).name()), __LINE__ , i) 
#else
  #define DUMP(i) 
#endif
 
#define TOSTRING(x) #x
#define SZ(x) (int)(x).size()
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(s) (s).begin(), (s).end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()) , v.end());

using namespace std;
typedef long long unsigned int llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;

struct Edge{
public:
  int from,to,cost;
  Edge(){}
  Edge(int _from,int _to,int _cost){
    from = _from;
    to = _to;
    cost = _cost;
  }
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
const int EPS = 1e-9;
const int MOD = 1e9+7;

int main (){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a,b;
  cin >> a >> b;
  int def = b-a;
  int cnt = 0;
  FOR(i,1,def){
    cnt += i;
  }
  int ans = cnt - a;
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		double a = sc.nextInt();
		double b = sc.nextInt();
		double c = sc.nextInt();
		double d = sc.nextInt();

		if (Math.ceil(a / d) >= Math.ceil(c / b)) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}

		sc.close();
	}

}


Measured memory_bytes: 35432
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <list>
#include <numeric>
#include <stack>
#include <iomanip>
#include <random>
#include <complex>
#include <functional>
#include <tuple>
#include <new>

using namespace std;

#define EPS (1e-9)
#define INF (1e9)
#define MOD (ll)(1e9 + 7)
#define PI (acos(-1))
#define REP(i,a,n) for(int i=a;i<n;i++)
#define rep(i, n) REP(i,0,n)
#define allof(a) (a).begin(), (a).end()

#define Yes(q) ((q) ? "Yes" : "No")
#define YES(q) ((q) ? "YES" : "NO")
#define Possible(q) ((q) ? "Possible" : "Impossible")
#define POSSIBLE(q) ((q) ? "POSSIBLE" ; "IMPOSSIBLE")

using ll = long long int;

ll gcd(ll a, ll b) {
    if (a < b) swap(a, b);
    if (b == 0) return a;
    return gcd(b, a % b);
}

ll beki(ll a, ll b) {
    ll tmp = 1;
    rep(i, b) tmp *= a;
    return tmp;
}

ll modPow(ll x, ll a) {
    if (a == 1) return x;
    if (a % 2) return (x * modPow(x, a - 1)) % MOD;
    ll t = modPow(x, a / 2);
    return ((t % MOD) * (t % MOD)) % MOD;
}

ll modInv(ll x) {
    return modPow(x, MOD - 2);
}

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

    cout << 1 - x << endl;
}

Measured memory_bytes: 3560
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 200001


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
   
    int n,w;
    cin>>n>>w;

    vector<pair<ll,ll>> v;

    for(int i=0;i<n;i++)
    {
    	ll x,y;
    	cin>>x>>y;
    	v.push_back(make_pair(x,y));
    }

    sort(v.begin(),v.end());

    ll dp[n+1][w+1];

    for(int i=0;i<n+1;i++)
    {
    	for(int j=0;j<w+1;j++)
    		if(i==0 || j==0)
    			dp[i][j]=0;
    }

    for(int i=1;i<n+1;i++)
    {
    	for(int j=1;j<w+1;j++)
    	{
    		ll a=v[i-1].first;
    		ll b=v[i-1].second;
    		if(j>=a)
	    		dp[i][j]=max(dp[i-1][j-a]+b,dp[i-1][j]);
	    	else
	    		dp[i][j]=dp[i-1][j];
    	}
    }

    cout<<dp[n][w];
}


Measured memory_bytes: 79232
import scala.collection.mutable
import scala.collection.mutable.ArrayBuffer

object methods {
  def solver(): Unit = {

    val tempList: Seq[Seq[String]] = {
      for (line <- io.Source.stdin.getLines()) yield {
        line.split(' ').toSeq
      }
    }.toSeq
    val N: Int = tempList(0)(0).toInt
    val numList: Seq[Int] = tempList(1).map(_.toInt)

    println(itar(numList, N))
  }

  //itareeeeさんの解法
  def itar(numList: Seq[Int], N: Int): Int = {
    val rangeMax: Int = numList.max + 1
    val numMax: Int = numList.max
    val buffer: ArrayBuffer[Int] = mutable.ArrayBuffer.fill(rangeMax)(0)
    for(i <- 0 until N){
      if(buffer(numList(i)) > 0) {
        buffer(numList(i)) = 2
      }else {
        numList(i).to(numMax).by(numList(i)).foreach(multiple => buffer(multiple) += 1)
      }
    }
    val ans = numList.count{x => buffer(x) == 1}
    ans
  }

  //愚直な解法
  def naive(numList: Seq[Int], N: Int): Int = {
    //一旦愚直にやってみるO(N*(N-1))
    var allCounter: Int = 0
    numList.zipWithIndex.foreach{v =>
      var i: Int = 0
      var counter: Int = 0
      while(i < N){//iが自分自身のインデックス以外で、割り切れなかったとき
        if(i != v._2 && v._1 % numList(i) != 0) counter += 1
        //任意の値で割り切れなかったとき、counterはN-1になるはず
        if(counter == N-1) allCounter += 1
        i += 1
      }
    }
    allCounter
  }

  //調和級数を用いた解法
  def harmonySeries(numList: Seq[Int], N: Int): Int = {
    val rangeMax: Int = numList.max + 1
    val numMax: Int = numList.max //重要！！x.to(numList.max)とするとだいぶ時間がかかる
    val buffer: ArrayBuffer[Int] = mutable.ArrayBuffer.fill(rangeMax)(0)

    //記録：O(A*logA)
    numList.distinct.foreach {x =>
      x.to(numMax).by(x).toList.foreach(v => if(buffer(v) <= 1) buffer(v) += 1)
      //for(v <- x.to(numMax).by(x)){if(v != x && buffer(v) == false) buffer(v) = true}
    }
    
    //値が1のインデックスを集計：リスト内の割り切れない数or割り切れない数の倍数：普通にやればO(A)、これはO(A*A*A)なってる？
    val includeMultipleIndexSet: Set[Int] = buffer.zipWithIndex.filter(x => x._1 <= 1).map(x => x._2).toSet
    val indexSet: Set[Int] = includeMultipleIndexSet.intersect(numList.toSet)
    //重複数字の集合を作りたい
    val duplicateNum: Set[Int] = numList.groupBy(identity).mapValues(_.size).map{
      case (key, value) => {
        if(value >= 2) key
        else 0
      }
    }.toSet

    val indivisibleList: List[Int] = indexSet.diff(duplicateNum).toList
    indivisibleList.length
  }
}

object Main extends App {
  methods.solver()
}


Measured memory_bytes: 83600
#include <array>
#include <deque>
#include <forward_list>
#include <list>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <iterator>
#include <algorithm>
#include <cfenv>
#include <random>
#include <numeric>
#include <cmath>
#include <iosfwd>
#include <iostream>
#include <ios>
#include <streambuf>
#include <istream>
#include <ostream>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <cstdlib>
#include<string>

#define SIZE 100002
typedef long long ll;
 
using namespace std;

int main(){
    string S;
    cin >> S;
    int n=(int)S.size();
    ll sum=0;
    for(int bit = 0 ; bit < (1<<n-1) ; bit++){
        ll sum_tmp = 0;
        for(int i = 0 ; i < n-1 ; i++){
            sum_tmp = sum_tmp*10 + (S[i] - '0');
            if(bit & (1<<i)){
                sum += sum_tmp;
                sum_tmp = 0;
            }
        }
        sum += sum_tmp*10 + (S[n-1] - '0');
    }
    cout << sum;
}

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

#define ll long long
#define pb push_back

const int maxn = 1e5 + 20;

vector<int> out[maxn] , in[maxn];

int pos[maxn] , sz;

bool visited[maxn];

void dfs(int v)
{
	visited[v] = 1;
	for(auto u : out[v])
		if(!visited[u])
			dfs(u);

	pos[v] = sz++;
}

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

	int n , m;
	cin >> n >> m;

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

		out[a].pb(b);
		in[b].pb(a);
	}

	for(int i = 0; i < n; i++)
		if(!visited[i])
			dfs(i);

	for(int i = 0; i < n; i++)
	{
		pair<int , int> mn = {1e9 , 0};
		for(auto u : in[i])
			mn = min(mn , make_pair(pos[u] , u + 1));

		cout << mn.second << endl;
	}
}










Measured memory_bytes: 14336
#include<bits/stdc++.h>
//g++ -std=c++11 

using namespace std;
typedef long long ll;

#define rep(i,n) for (long long i = 0; i < (n); ++i)
#define DIV 1000000007 //10^9+7

int main(){
	ll A, B;
	cin >> A >> B;
	ll ans = -1000000;
	ans = max(ans, A + B);
	ans = max(ans, A - B);
	ans = max(ans, A * B);
	cout << ans << endl;
}

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

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	string a,b;
	string e;
	int c,d;
	cin>>a>>b>>c>>d;
	cin>>e;
	if(a==e){
		c--;
	}
	if(b==e){
		d--;
	}
	cout<<c<<" "<<d<<endl;
	
	
}


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

typedef long long lint;
typedef pair<int, int> pint;
#define x first
#define y second

int n, a[100004];

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

	for (int i=0; i<n; i++) scanf("%d", a+i);

	int ans=1;
	for (int i=0; i<n; i++) ans ^= a[i]&1;

	puts(ans ? "YES" :"NO");
}


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

class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long sum = 0;
		for(int i=1;i<=n;i++){
			if(i%3!=0 && i%5!=0){
				sum += (long)i;
			}
		}
		System.out.println(sum);
	}
}

Measured memory_bytes: 35804
from itertools import permutations
n,C=map(int,input().split())
d=[list(map(int,input().split())) for _ in range(C)]
c=[list(map(int,input().split())) for _ in range(n)]
a=[[0]*C for _ in range(3)]
for i in range(n):
	for j in range(n):
		a[(i+j)%3][c[i][j]-1]+=1
ans=10**9
for v in permutations(range(C),3):
	tmp=0
	for i in range(3):
		for j in range(C):
			tmp+=a[i][j]*d[j][v[i]]
	ans=min(ans,tmp)
print(ans)

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

int n;
string s[15];
vector<int> num[15];
int csn;
bool used[10];
int v[10];
int ans;
void dfs(int idx) {
	if(idx == csn) {
		int sum1 = 0;
		for(int i = 0; i < n - 1; ++i) {
			if(v[num[i][0]] == 0 and 1 < (int)num[i].size()) {
				return;
			}
			int tmp = 0;
			for(int j : num[i]) {
				tmp *= 10;
				tmp += v[j];
			}
			sum1 += tmp;
		}
		int sum2 = 0;
		for(int j : num[n - 1]) {
			if(v[num[n - 1][0]] == 0 and 1 < (int)num[n - 1].size()) {
				return;
			}
			sum2 *= 10;
			sum2 += v[j];
		}
		if(sum1 == sum2) {
			ans++;
		}
		return;
	}
	for(int i = 0; i < 10; ++i) {
		if(used[i]) continue;
		used[i] = 1;
		v[idx] = i;
		dfs(idx + 1);
		used[i] = 0;
		v[idx] = -1;
	}
}

int main() {
	while(cin >> n and n > 0) {
		ans = 0;
		set<char> cs;
		for(int i = 0; i < n; ++i) {
			cin >> s[i];
			for(char c : s[i]) {
				cs.insert(c);
			}
		}
		csn = cs.size();
		for(int i = 0; i < n; ++i) {
			num[i] = {};
			for(char c : s[i]) {
				int id = 0;
				for(char cc : cs) {
					if(cc == c) {
						num[i].push_back(id);
					}
					id++;
				}
			}
		}
		dfs(0);
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 3076
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
sum = 0
for i in range(N):
  sum += int(b[a[i]-1])
  if(i != 0):
    if(a[i] - a[i-1] == 1):
      sum += int(c[a[i-1]-1])
print(sum)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define quick                    \
    ios::sync_with_stdio(false); \
    cin.tie(0);
#define time cerr << (0.1 * clock()) / CLOCKS_PER_SEC << endl;
#define mod 1000000007
typedef long long ll;
typedef pair<ll, ll> pl;
#define forn(n) for (ll i = 0; i < ll(n); i++)

void solve() {
    int s, w;
    cin >> s >> w;
    cout << (w >= s ? "unsafe" : "safe") << '\n';
}

int main() {
    quick;
    solve();
    // ll t;
    // cin >> t;
    // while (t--) {
    //     solve();
    // }
}

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

#define REP(i,n) for(int i=0;i<(n);i++)
#define REAP(i,a,n) for(int i=(a);i<(n);i++)
#define YES cout<<"Yes"<<endl
#define NO cout<<"No"<<endl
#define fr first
#define sc second
#define pb push_back
#define All(v) v.begin(),v.end()
typedef long long ll;

int main(){
    ios::sync_with_stdio(false);

    string s;
    cin >> s;

    bool flg=true;

    if(s[0]!='A')flg=false;
    if(s[1]<'a'||'z'<s[1])flg=false;
    int cou=0;
    REAP(i,2,s.size()-1){
        if(s[i]=='C')cou++;
        else if('a'>s[i]||s[i]>'z')flg=false;
    }
    if(cou!=1)flg=false;
    if(s[s.size()-1]<'a'||s[s.size()-1]>'z')flg=false;

    if(flg)cout << "AC\n";
    else cout << "WA\n";

    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        double r;
        
        r = scanner.nextDouble();
        
        System.out.println(String.format("%.6f",r*r*Math.PI) + " " + String.format("%.6f",2*r*Math.PI));
        
    }
}


Measured memory_bytes: 28104
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<stack>
using namespace std;
#define ll long long
#define ull unsigned long long
#define up(i,a,b) for(auto i=(a);i<=(b);i++)
#define down(i,a,b) for(auto i=(a);i>=(b);i--)
#define mem(x,y) memset(x,(y),sizeof x)
#define ff first
#define ss second
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define sc(a) scanf("%d",&a)
#define scl(a) scanf("%I64d",&a)
#define scs(a) scanf("%s",a)
#define pr(a,b) printf("%d%c",a,b)
#define prl(a,b) printf("%I64d%c",a,b)
#define PQ priority_queue
#define ld long double
#define all(v) v.begin(),v.end()
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define GG {gg++;break;}

typedef pair<ll,int> pii;
typedef map<int,int> mii;
typedef vector<int> V;

template<typename T>
inline void read(T& input) {
	input=0;
	int v=1;
	char c=getchar();
	while((c<'0'||c>'9')&&c!='-')c=getchar();
	if(c=='-')v=-1,c=getchar();
	while(c>='0'&&c<='9')input=input*10+c-'0',c=getchar();
	input*=v;
}

int a[210];
int main() {
	int n,ans=0;sc(n);
	up(i,1,n+n)sc(a[i]);
	sort(a+1,a+1+2*n);
	up(i,1,2*n)ans+=a[i++];
	pr(ans,'\n');
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;

int main(){
    int n,k;
    cin >> n >> k;
    int count = 1;
    while(k > n){
        k = (k+1)/2;
        count++;
    }
    double p = (n-k+1)*pow(0.5,count-1)/n;
    while(k > 1){
        int l = (k+1)/2 ;
        p += (k-l)*pow(0.5,count)/n;
        count++;
        k = l;
    }
    cout << setprecision(12) <<  p << endl;

    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>

using namespace std;

#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 FORR(i, m, n) for(int i = n;i >= m;i--)
#define REPO(i, n) for(int i = 1;i <= n;i++)
#define ll long long
#define INF 1999999999
#define MINF -1999999999
#define ALL(n) n.begin(),n.end()

int main() {
	int a, b;
	cin >> a >> b;
	if (a % 500 <= b)cout << "Yes" << endl;
	else cout << "No" << endl;
}

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

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) cin >> A.at(i);
  
  int min = 1000000000, max = 1;
  for (auto e : A) {
    if (e < min) min = e;
    if (e > max) max = e;
  }
  
  cout << max - min << endl;
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
#define collect(arr, size) rep(i,size) cin >> arr[i];
#define int long long

void printline(int n, string s="a", char maxchar = 'b'){
    if(n==s.length()){
        printf("%s\n",s.c_str());
        return;
    }
    for(char c='a'; c <= maxchar; c++){
        char next = (c==maxchar) ? maxchar+1 : maxchar;
        printline(n,s+(char)(c),next);
    }
}

signed main(){
    int N; cin >> N;
    printline(N);
}

Measured memory_bytes: 1536
# ABC 120: B – K-th Common Divisor
a, b, k = [int(s) for s in input().split()]

divisors = []

for i in range(1, min(a, b) + 1):
    if a % i == 0 and b % i == 0:
        divisors.append(i)

divisors.sort(reverse=True)

print(divisors[k - 1])

Measured memory_bytes: 2940
#include <stdio.h>

int main() {
    int i, k, v,an1,an2,suu;
    int MAX_V = 10000;
    int prime[MAX_V+1];
    for(i = 0; i <= MAX_V; i++) {
        prime[i] = 1;
    }
    for(i = 2; i*i <= MAX_V; i++) {
        if(prime[i]) {
            for(k = 2 * i; k <= MAX_V; k += i) {
                prime[k] = 0;   
            } 
        }
    }
   while(1){
        scanf("%d",&suu);
        if(suu != 0){
            for(k=2;k<=suu;k++){
            	if(prime[k-2]==1 && prime[k]==1){
        	    	an1=k-2;
        	    	an2=k;
            	}
            }
            printf("%d %d\n",an1,an2);
        }
        else{
    	    break;
        }
    }
    return 0; 
}

Measured memory_bytes: 1068
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
const int mod = 1000000007;
const ll INF = 1001001001;
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; }

ll dp[110000];

int main(){
    int n;
    cin >> n;
    vector<ll> h(n);
    rep(i,n) cin >> h[i];
    rep(i,n) dp[i] = INF;
    dp[0] = 0;

    for(int i=0;i<n-1;i++){
        chmin(dp[i+1],dp[i]+abs(h[i]-h[i+1]));
        chmin(dp[i+2],dp[i]+abs(h[i]-h[i+2]));
    }

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

Measured memory_bytes: 1792
A, B = list(map(int, input().split()))

priA = A * 100 // 108
priB = B * 100 // 110

for i in range(100000):
    if int(0.08 * i) == A and int(0.1 * i) == B:
        print(i)
        break

else:
    print(-1)

Measured memory_bytes: 3060
#include<algorithm>
#include<vector>
template<typename T, T INF>
class SegmentTree {
 public:
  SegmentTree(int n) : size_(1) {
    while(size_ < n) size_ <<= 1;
    node_.assign(size_ << 1, 0);
    lazy_.assign(size_ << 1, 0);
  }
  T find(int left, int right) {return find(left, right + 1, 1, 0, size_);}
  void add(int left, int right, T value) {add(left, right + 1, value, 1, 0, size_);}
 private:
  inline int left_child(int node) const {return node << 1;}
  inline int right_child(int node) const {return (node << 1) + 1;}
  inline T merge(T vl, T vr) const {return std::max(vl, vr);}
  inline void propagate(int k) {
    if(k < size_) {
      lazy_.at(left_child(k)) += lazy_.at(k);
      lazy_.at(right_child(k)) += lazy_.at(k);
    }
    node_.at(k) += lazy_.at(k);
    lazy_.at(k) = 0;
  }
  T find(int a, int b, int k, int l, int r) {
    propagate(k);
    if(b <= l || r <= a) return -INF;
    if(a <= l && r <= b) return node_.at(k) + lazy_.at(k);
    auto vl = find(a, b, left_child(k), l, (l + r) / 2);
    auto vr = find(a, b, right_child(k), (l + r) / 2, r);
    return merge(vl, vr);
  }
  T add(int a, int b, T value, int k, int l, int r) {
    propagate(k);
    if(b <= l || r <= a) return node_.at(k);
    if(a <= l && r <= b) return node_.at(k) + (lazy_.at(k) += value);
    auto vl = add(a, b, value, left_child(k), l, (l + r) / 2);
    auto vr = add(a, b, value, right_child(k), (l + r) / 2, r);
    return node_.at(k) = merge(vl, vr);
  }
  int size_;
  std::vector<T> node_;
  std::vector<T> lazy_;
};

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

int main() {
  const int INF = 1e6;

  int W, H, N;
  cin >> W >> H >> N;

  SegmentTree<int, INF> T(INF);
  for(auto i = 0; i < N; ++i) {
    int x, y;
    cin >> x >> y;
    if(T.find(x, x) < y) T.add(x, x, y - T.find(x, x));
  }

  int res = INF;

  for(auto x = 0; x < INF; ++x) {
    res = min(res, x + T.find(x + 1, INF));
  }

  cout << res << endl;
}

Measured memory_bytes: 19196
#include <stack>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#define pb push_back
#define sp " "
#define sl "\n"
#define fi first
#define se second
#define mp make_pair
#define sz(a) ((int)a.size())
#define all(a) a.begin(),a.end()
#define rev(a) reverse(a.begin(),a.end())

using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;

const int N=1e6+5,mod=1000000007;
ll n,a[N],b[N],c;
int main() {
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(0);
	cin>>n; for (int i=1;i<=n;i++) cin>>a[i];
	for (int i=1;i<=n;i++) if (i>=a[i]) b[i-a[i]]++;
	for (int i=1;i<=n;i++) if (a[i]+i<=n) c+=b[a[i]+i];
	cout<<c;
	return 0;
}


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

using namespace std;

using ll = long long;
using dd = double;
using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<dd>;
using vb = vector<bool>;

template <class T, class V>
istream& operator>>(istream& in, pair<T, V>& pair) {
    return in >> pair.first >> pair.second;
}

template <class T>
istream& operator>>(istream& in, vector<T>& elements) {
    for (size_t i = 0; i < elements.size(); ++i) {
        in >> elements[i];
    }
    return in;
}

template <class Container, class Element>
bool Contains(const Container& container, const Element& element) {
    return container.find(element) != container.end();
}

template <class T>
ostream& operator<<(ostream& out, const vector<T>& elements) {
    for (const T& element : elements) {
        out << element << ' ';
    }
    return out;
}

template <class T, class V>
ostream& operator<<(ostream& out, const pair<T, V>& pair) {
    out << pair.first << ' ' << pair.second;
}

#define FOR(i,n) for(size_t i=0, i##_len=(n); i<i##_len; ++i)
#define SORT(c) sort((c).begin(), (c).end())

using Graph = vector<unordered_set<int>>;

int main() {
    ios_base::sync_with_stdio(false);
    
    int n, m;
    cin >> n >> m;
    
    Graph g(3 * n);
    FOR(i, m) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        
        g[3 * u].insert(3 * v + 1);
        g[3 * u + 1].insert(3 * v + 2);
        g[3 * u + 2].insert(3 * v);
    }
    
    int s, t;
    cin >> s >> t;
    s = (s - 1) * 3;
    t = (t - 1) * 3;
    
    
    queue<int> q;
    vb used(3 * n);
    vi dist(3 * n, -1);
    
    q.push(s);
    used[s] = true;
    dist[s] = 0;
    
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        
        assert(used[v]);
        for (int next : g[v]) {
            if (used[next]) {
                continue;
            }
            used[next] = true;
            dist[next] = dist[v] + 1;
            q.push(next);
        }
    }
    
    assert(dist[t] == -1 || dist[t] % 3 == 0);
    cout << ((dist[t] == -1) ? -1 : dist[t] / 3) << endl;
    
    return 0;
}


Measured memory_bytes: 36608
N = gets.to_i
S = gets.chomp

ee = ew = 0
we = ww = 0
N.times do |i|
  we += 1 if S[i] == 'E'
  ww += 1 if S[i] == 'W'
end

ans = 1000000
N.times do |i|
  we -= 1 if S[i] == 'E'
  ww -= 1 if S[i] == 'W'
  ans = [ans, ew + we].min
  ee += 1 if S[i] == 'E'
  ew += 1 if S[i] == 'W'
end

puts ans


Measured memory_bytes: 2572
/*#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 998244353
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
int a,b;
int main(){
	cin >> a >> b;
	if(a%2 != b%2) puts("IMPOSSIBLE");
	else cout << (a+b)/2 << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
	long long i, j, k, N, a[100], ans=0;
	cin >> N;
	for (i = 0; i < N; i++) {
		cin >> a[i];
	}

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

	for (i = N-1; i > 0; i--) {
		ans += (a[i] - a[i - 1]);
	}

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

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;} return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;} return 0;}
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) vec.begin(),vec.end()
typedef long long ll;
typedef pair<ll,ll> l_l;
typedef pair<int,int> i_i;
const ll MOD=1e9+7;
const int INF=1<<30;

int main(){
  ll N,K;
  cin >> N >> K;
  vector<ll> h(N);
  rep(i,N) cin >> h[i];
  priority_queue<ll> que;
  rep(i,N){
    que.push(h[i]);
  }
  if(K>=N){
    cout << 0 << endl;
    return 0;
  }
  rep(i,K){
    que.pop();
  }
  ll ans=0;
  rep(i,N-K){
    ans+=que.top();
    que.pop();
  }
  cout << ans << endl;
}

Measured memory_bytes: 3956
#3 Range Flip Find Route
h,w = map(int,input().split())
s= [None for i in range(h)]
for i in range(h):
    s[i] = input()
    
dp = [[0]*w for i in range(h)]

now=0
if s[0][0]=="#":
    now+=1
    dp[0][0]=now
for i in range(1,w):
    if s[0][i-1]=="." and s[0][i]=="#":
        now+=1
    dp[0][i]=now
        
now=0
if s[0][0]=="#":
    now+=1
for i in range(1,h):
    if s[i-1][0]=="." and s[i][0]=="#":
        now+=1
    dp[i][0]=now

for i in range(1,h):
    for j in range(1,w):
        cand1 = dp[i-1][j] + (s[i-1][j]=="." and s[i][j]=="#")
        cand2 = dp[i][j-1] + (s[i][j-1]=="." and s[i][j]=="#")
        dp[i][j]=min(cand1,cand2)
        
print(dp[-1][-1])

Measured memory_bytes: 42736
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
#include <functional>
#include <cassert>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)
#define ALL(v) v.begin(),v.end()
template < class T > inline bool chmax(T& a, T b) {if (a < b) { a=b; return true; } return false; }
template < class T > inline bool chmin(T& a, T b) {if (a > b) { a=b; return true; } return false; }
#define DEBUG_VLL(vec) REP(sz, vec.size()) std::cerr<<vec[sz]<<(sz==vec.size()-1?'\n':' ');

const long long MOD = 1000000007;
const long long HIGHINF = (long long)1e18;
const int INF = (int)1e9;

int n;
vll a;
V< V<int> > edges;
V<int> ans;
vll dp;

void dfs(int i, int p) {
    int idx = lower_bound(ALL(dp), a[i]) - dp.begin();
    ll tmp = dp[idx];
    dp[idx] = a[i];
    ans[i] = lower_bound(ALL(dp), HIGHINF) - dp.begin();
    
    for (int e: edges[i]) {
        if (e == p) continue;
        dfs(e, i);
    }
    dp[idx] = tmp;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    a.resize(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    edges.resize(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        u--, v--;
        edges[u].emplace_back(v);
        edges[v].emplace_back(u);
    }

    ans.resize(n);
    dp.resize(n, HIGHINF);
    dfs(0, -1);

    for (int i = 0; i < n; i++) cout << ans[i] << '\n';
    return 0;
}


Measured memory_bytes: 29512
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string>
#include <map>

using namespace std;

typedef long long ll;

void solver_main()
{
	int a;
	string s;
	cin >> a;
	cin >> s;
	if (a >= 3200) {
		cout << s << endl;
	}
	else {
		cout << "red" << endl;
	}

}

int main(void)
{
	solver_main();
	return 0;
}

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

int main() {
  int N;
  cin >> N;
  string S[N];
  for(int i=0; i<N; i++) {
    cin >> S[i];
  }
  sort(S, S+N);
  int ans=1;
  for(int i=1; i<N; i++) {
    if(S[i]!=S[i-1]) {
      ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 9884
#!/usr/bin/env python3
import sys


def solve(S: str):
    if S == "Sunny":
        print("Cloudy")
    elif S == "Cloudy":
        print("Rainy")
    else:
        print("Sunny")
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    x,t=INTM()
    if x>=t:
        print(x-t)
    else:
        print('0')
if __name__ == '__main__':
    do()

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int mod = 1e9+7;

int main(){
    string s;
    cin >> s;
    vector<int> ans;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == '0') ans.push_back(0);
        else if(s[i] == '1') ans.push_back(1);
        else if(!ans.empty() && s[i] == 'B') ans.pop_back(); 
    }    
    for(int i = 0; i < ans.size(); i++){
        cout << ans[i];
    }
}

Measured memory_bytes: 256
package main

import "fmt"

func getSum(n int) (s int) {
	s = 0
	for n > 0 {
		s += n % 10
		n = n / 10
	}
	return
}

func main() {
	var n, a, b int
	fmt.Scan(&n, &a, &b)
	sum := 0
	for i := 1; i <= n; i++ {
		if a <= getSum(i) && getSum(i) <= b {
			sum += i
		}
	}
	fmt.Println(sum)
}


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

int main(){
  int n;
  cin >> n;
  
  int a[n];
  
  for(auto &i:a)cin >> i;
  
  int ans = 0;
  
  for(int i = 1;i<n-1;i++){
    if((a[i-1]<a[i] && a[i]<a[i+1])|| (a[i-1]>a[i] && a[i]>a[i+1]))ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;

namespace lineAralgebra
{
	class Program
	{
		public static void Main(String[] args)
		{
			var input = Console.ReadLine().Split().Select(int.Parse).ToArray();
			int n = input[0];
			var m = input[1];

			var correctSet = new HashSet<int>();
			// var wrongSet = new HashSet<int>();
			var wrongCount = 0;
			var p_count = new int[n + 1];

			for (var i = 0; i < m; i++)
			{
				var a = Console.ReadLine().Split();
				var p = int.Parse(a[0]);
				var s = a[1];

				if (s == "AC" && !correctSet.Contains(p))
				{
					correctSet.Add(p);
				}
				else if (s == "WA" && !correctSet.Contains(p))
				{
					p_count[p]++;
				}
			}

			foreach (var set in correctSet)
			{
				wrongCount += p_count[set];
			}

			System.Console.WriteLine(correctSet.Count + " " + wrongCount);
		}
	}
}



Measured memory_bytes: 19916
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")



#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <memory>
#include <cassert>
#include <cstdio>
#include <cmath>
#include <string>
#include <unordered_map>
#include <iomanip>
#include <ctime>
#include <sstream>  
#include <deque>
#include <unordered_set>
#include <stack>
#include <functional>
#include <memory.h>
#include <bitset>
#include <numeric>

using namespace std;

//#define int long long
vector <vector <int> > g;
vector <int> used;
void dfs(int v) {
    used[v] = 1;
    int cnt = 0;
    for (auto it : g[v]) {
        if (!used[it]) {
            dfs(it);
            cnt++;
        }
    }
    if (cnt > 1) {
        cout << "NO" << endl;
        exit(0);
    }
}
signed main() {

    vector <int> cnt(5);
    g.resize(5);
    used.resize(5);
    for (int i = 1; i <= 3; ++i) {
        int a, b;
        cin >> a >> b;
        cnt[a]++;
        cnt[b]++;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (int i = 1; i <= 4; ++i) {
        if (cnt[i] == 1) {
            dfs(i);
            for (int j = 1; j <= 4; ++j) {
                if (!used[j]) {
                    return 0 * printf("NO");
                }
            }
            return 0 * printf("YES");
        }
    }
    cout << "NO" << endl;
}

Measured memory_bytes: 256