akhauriyash/Code-Regression huggingface dataset:
# include <bits/stdc++.h>
using namespace std; 
int main(){
 long long int n,sum,temp,i;
 string str; 
  cin>>str; 
  n=str.length();
  /*temp=floor(log10((double)n))+1;
  cout<<temp; */
  sum=0;
  for(i=0;i<n;i++){
    sum=sum+(str[i]-'0');
  }
  if(sum%9==0){
    cout<<"Yes";
  }
  else{
    cout<<"No";
  }
  return 0;
}

Measured memory_bytes: 3704
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n=int(input())
v=tuple(tuple(map(lambda x: int(x)-1,input().split())) for _ in range(n-1))

node=[[] for _ in range(n)]
k=0
used=[-1]*n
seen=[-1]*n
for pair in v:
    node[pair[0]].append(pair[1])
    node[pair[1]].append(pair[0])
    k=max(k,len(node[pair[0]]),len(node[pair[1]]))
print(k)
ans={}
d=deque()
d.append(0)
while d:
    i=d.pop()
    seen[i]=1
    res=1
    for j in node[i]:
        if seen[j]==1:
            continue
        d.appendleft(j)
        if res!=used[i]:
            ans[(i,j)]=res
        else:
            res+=1
            ans[(i,j)]=res
        used[j]=res
        res+=1
for pair in v:
    a,b=pair
    if (a,b) in ans:
        print(ans[(a,b)])
    else:
        print(ans[(b,a)])
    

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

ret = 0 # 倒した数

for i in range(N):
    k = A[i] - B[i]
    
    if k < 0: # 勇者の余力あり
        ret += A[i]

        if (A[i+1] + k) > 0:
            A[i+1] += k
            ret += abs(k)
        else:
            ret += A[i+1]
            A[i+1] = 0
    else:
        ret += B[i]
        
print(ret)

Measured memory_bytes: 19156
S=input()
N=len(S)
def is_kaibun(a,b):#ind a~b
    for i in range(a,b+1):
        if i>=b-i:
            break
        if S[i]!=S[b-i]:
            return False
    return True
if is_kaibun(0,(N-3)//2) and is_kaibun((N+1)//2,N-1) and is_kaibun(0,N-1):
    print("Yes")
else:
    print("No")    


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

int mod = 1000000007;
int64_t large = 9223372036854775807;
double PI = 3.141592653589793;

int main()
{
    int N, K;
    cin >> N >> K;
    vector<int> hist(200000);
    for (int i = 0; i < N; i++)
    {
        int tmp;
        cin >> tmp;
        hist[tmp - 1]++;
    }
    sort(hist.begin(),hist.end());
    reverse(hist.begin(), hist.end());
    int count = 0;
    for (int i = 0; i < K; i++)
        count += hist[i];
    
    cout << N - count;
}

Measured memory_bytes: 1024
# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate,permutations, combinations,combinations_with_replacement,product

def resolve():

    N,M=map(int,input().split())
    A=[list(map(int,input().split())) for i in range(M)]

    for k in range(1,N+1):
        cnt=0
        for i in A:
            for j in i:
                if j==k:
                    cnt+=1
        print(cnt)

        

resolve()

Measured memory_bytes: 40176
#include<cstdio>


int main(void)
{
	int n;
	char s[100+2];

	while(scanf("%d%100s", &n, s)==2)
	{
		int red=0;

		for(int i=0;i<n;i++)
		{
			if(s[i]=='R') red++;
		}

		int blue=n-red;

		int ans=(red>blue);

		printf("%s\n", ans?"Yes":"No");
	}

	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <limits>
#include <math.h>
#include <cmath>
#include <cctype>
#include <cstdio>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int> ;
using vs = vector<string>;
using vb = vector<bool>;
using vll = vector<long long>;
using vvll = vector<vector<long long >>;
#define PI  3.1415926535
#define rep(i, k, n) for(ll i = k; i < n; i++)

int main(){
  ll n, k; cin >> n >> k;
  vll res(n);
  rep(i, 0, n){cin >> res[i];}
  
  ll loop_start_village;
  ll loop_start_index;
  ll loop_cycle;
  
  vll village_index(0);
  vb num_check(n+1,false);
  
  village_index.emplace_back(1);
  num_check[1] = true;
  
  rep(i, 0, n){
    if(num_check[res[village_index[i]-1]]){
      loop_start_village = res[village_index[i]-1];
      break;
    }
    village_index.emplace_back(res[village_index[i]-1]);
    num_check[res[village_index[i]-1]] = true;
  }
  
  rep(i, 0, village_index.size()){
    if(village_index[i] == loop_start_village){
      loop_start_index = i;
      break;
    }
  }
  loop_cycle = village_index.size() - loop_start_index;
  
  //cout << loop_start_village << endl;
  //cout << loop_start_index << endl;
  //cout << loop_cycle << endl;
  
  if(k < village_index.size()){cout << village_index[k] << endl;}
  else{
    k -= loop_start_index;
    k %= loop_cycle;
    k += loop_start_index;
    cout << village_index[k] << endl;
  }
}



Measured memory_bytes: 6852
#include <bits/stdc++.h>
using namespace std;
const int dh[9] = {0, 1, 0, -1, -1, 1, 1, -1, 0};
const int dw[9] = {1, 0, -1, 0, 1, 1, -1, -1, 0};

int main() {
    long long h, w;
    int n;
    cin >> h >> w >> n;
    set<pair<int, int>> v;
    set<pair<int, int>> s;
    for (int _ = 0; _ < n; _++) {
        int a, b;
        cin >> a >> b;
        s.emplace(--a, --b);
        for (int i = 0; i < 9; i++) {
            int di = a + dh[i], dj = b + dw[i];
            if (di <= 0 || h-1 <= di || dj <= 0 || w-1 <= dj) continue;
            v.emplace(di, dj);
        }
    }
    
    map<int, long long> cnt;
    long long zero = (h-2) * (w-2);
    for (const auto& e : v) {
        int a, b; tie(a, b) = e;
        int black = 0;
        for (int i = 0; i < 9; i++) {
            int di = a + dh[i], dj = b + dw[i];
            if (di < 0 || h <= di || dj < 0 || w <= dj) continue;
            if (s.count(make_pair(di, dj))) black++;
        }
        cnt[black]++;
        zero--;
    }
    
    vector<long long> ans(10);
    ans[0] = zero;
    for (const auto& e : cnt) ans[e.first] = e.second;
    for (const auto& e : ans) cout << e << endl;
    return 0;
}

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

int main(){
    int N;
    cin >> N;
    vector<int> d(N);
    for(int i=0;i<N;i++){
        cin >> d.at(i);
    }
    sort(d.begin(),d.end());
    int c=1;
    for(int i=1;i<N;i++){
        if(d.at(i)!=d.at(i-1)) c++;
    }
    cout << c << endl;
    return 0;
}

Measured memory_bytes: 256
use proconio::input;
use std::collections::HashMap;

fn helper(mut n: usize) -> (usize, usize) {
  let a = n % 10;
  let mut b = 0;
  while 0 < n {
    b = n;
    n /= 10;
  }
  (a, b)
}

fn main() {
  input! {
    n: usize,
  }

  let mut map: HashMap<(usize, usize), usize> = HashMap::new();
  for i in 1..=n {
    let p = helper(i);
    let mut entry = map.entry(p).or_insert(0);
    *entry += 1;
  }

  let mut count = 0;
  for i in 1..=n {
    let (a, b) = helper(i);
    count += map.get(&(b,a)).unwrap_or(&0);
  }

  println!("{}", count);
}

Measured memory_bytes: 2200
#include <iostream>

using namespace std;
   
int main(){
    while(true){
    int a,b;
    char op;
    cin>>a>>op>>b;
    
    switch(op){
        case '+':
            cout<<a+b<<endl;
            break;
        case '-':
            cout<<a-b<<endl;
            break;
        case '*':
            cout<<a*b<<endl;
            break;
        case '/':
            cout<<a/b<<endl;
            break;
        case '?':
            return 0 ;
    }
    }
}



Measured memory_bytes: 3092
#include <bits/stdc++.h>
#define int long long
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;

signed main(){
	int q;
	set<int>s;
	cin>>q;
	while(q--){
		int x,y;
		cin>>x>>y;
		if(x==1)cout<<s.count(y)<<endl;
		else if(!x){
			s.insert(y);
			cout<<s.size()<<endl;
		}
		else if(x==2)s.erase(y);
		else{
			int l=y,r;
			cin>>r;
			set<int>::iterator end,it;
			it=s.lower_bound(l);
			end=s.upper_bound(r);
			for(;it!=end;it++){
				cout<<(*it)<<endl;
			}
		}
	}
}


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

#define ll long long
int k;

void solve() {
	cin>>k;
	int ans=1,deg=k;
	while(deg%360) {
		deg+=k;
		ans++;
	}
	cout<<ans<<'\n';
}

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

		solve();
	return 0;
}


Measured memory_bytes: 3604
#include<bits/stdc++.h>
using namespace std;
int N,K;
int main(){
    cin>>N>>K;double sum=0.0,tmpsum=1.0;
    for(int i=1;i<=N;i++){
        int num=i;
        while(num<K){tmpsum*=0.5;num*=2;}
        sum+=tmpsum;
        tmpsum=1.0;
    }
    double score=(1/(double)N)*sum;
    printf("%.12f",score);
}

Measured memory_bytes: 256
const solve = (c, blist, alist) => {
  // ...
  let result = 0
  alist.map((as) => {
    const m = as
      .map((a, i) => {
        return a * blist[i]
      })
      .reduce((curr, next) => {
        return curr + next
      }, 0)
    if (m + c > 0) {
      result++
    }
  })
  return result
}

const main = (input) => {
  const [head, b, ...as] = input.split("\n")
  const [n, m, c] = head.split(" ").map(Number)
  const blist = b.split(" ").map(Number)
  const alist = as.map((a) => {
    return a.split(" ").map(Number)
  })

  return solve(c, blist, alist)
}

if (process.env.NODE_ENV !== "test") {
  const input = require("fs").readFileSync("/dev/stdin", "utf8")
  console.log(main(input.trim()))
}

Measured memory_bytes: 7500
#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define int long long

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

    string s;
    cin >> s;
    bool ans = (s.find('7') != string::npos);
    cout << (ans ? "Yes" : "No") << endl;
}


Measured memory_bytes: 3096
#include<bits/stdc++.h>
using namespace std;
const int maxn=200009;

int n;

int a,b,c,p;
char s[maxn];

int ans[maxn];
int popcount(int x){
	int ret=0;
	while(x){
		ret+=x&1;x>>=1;
	}
	return ret;
}

int g(int x){
	int ret=0;
	while(x){
		++ret;x=x%popcount(x);
	}
	return ret;
}

void work(int type,int p){
	if(p==0)return;
	int sum=0;
	for(int i=n-1;i>=0;--i)sum=(sum*2+s[i]-'0')%p;
	int b=1%p;
	for(int i=0;i<n;++i,b=b*2%p){
		if(s[i]-'0'!=type)continue;
		int nsum;
		if(type==0)nsum=(sum+b)%p;
		else nsum=(sum-b+p)%p;
		ans[i]=g(nsum)+1;
	}
}
int main(){
	scanf("%d",&n);
	scanf("%s",s);
	reverse(s,s+n);
	for(int i=0;i<n;++i)p+=s[i]=='1';
	work(0,p+1);
	work(1,p-1);
	for(int i=0;i<n;++i)printf("%d\n",ans[n-i-1]);
	return 0;
}

Measured memory_bytes: 4780
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(int i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(int i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(int i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define uniq(x) (x).erase(unique((x).begin(), (x).end()), (x).end())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // std::ifstream in("input.txt");
    // std::cin.rdbuf(in.rdbuf());
    const ll inf = 1e15;
    ll n, m, l;
    cin >> n >> m >> l;
    vector<vector<ll>> dist(n, vector<ll>(n, inf));
    rep(i, n) dist[i][i] = 0;
    rep(i, m) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        if (l < c) continue;
        dist[a][b] = c;
        dist[b][a] = c;
    }
    rep(i, n) {
        rep(ii, n) {
            rep(iii, n) {
                dist[ii][iii] = min(dist[ii][iii], dist[ii][i] + dist[i][iii]);
            }
        }
    }
    vector<vector<ll>> supply(n, vector<ll>(n, inf));
    rep(i, n) {
        rep(ii, n) {
            if (i == ii) continue;
            if (dist[i][ii] <= l) supply[i][ii] = 1;
        }
    }
    rep(i, n) {
        rep(ii, n) {
            rep(iii, n) {
                supply[ii][iii] = min(supply[ii][iii], supply[ii][i] + supply[i][iii]);
            }
        }
    }
    int q;
    cin >> q;
    rep(i, q) {
        int s, t;
        cin >> s >> t;
        s--; t--;
        if (supply[s][t] == inf) {
            cout << -1 << endl;
        }
        else {
            cout << (supply[s][t] - 1) << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 1920
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <queue>
#include <iomanip>
#include <map>

#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define P pair<int, int>
#define ll long long

using namespace std;
int mod = 1000000007;

int N;
vector<P> X;
vector<P> Y;
vector<P> graph[100005];

int main() {

  cin >> N;

  rep(i, N) {
    int x, y;
    cin >> x >> y;
    X.emplace_back(x, i);
    Y.emplace_back(y, i);
  }

  sort(X.begin(), X.end());
  sort(Y.begin(), Y.end());

  rep(i, N-1) {
    int len = X.at(i+1).first - X.at(i).first;
    int u = X.at(i+1).second;
    int v = X.at(i).second;
    graph[u].emplace_back(v, len);
    graph[v].emplace_back(u, len);

    len = Y.at(i+1).first - Y.at(i).first;
    u = Y.at(i+1).second;
    v = Y.at(i).second;
    graph[u].emplace_back(v, len);
    graph[v].emplace_back(u, len);
  }

  ll ans = 0;
  priority_queue<P, vector<P>, greater<>> que;
  vector<bool> used(N);
  que.emplace(0, 0);

  while (!que.empty()) {
    P pair = que.top(); que.pop();
    int u = pair.second;
    if (used.at(u)) continue;
    used.at(u) = true;
    ans += pair.first;
    for (auto &e : graph[u]) {
      if (!used.at(e.first)) {
        que.emplace(e.second, e.first);
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 10860
N = int(input())
XL = []
for i in range(N):
    xl = list(map(int, input().split()))
    XL.append(xl)

SE = []
for x, l in XL:
    s = x - l
    e = x + l
    SE.append([s, e])

SE.sort(key=lambda x:x[1])
# print(SE)

cnt = 1
st = SE[0][1]
for s, e in SE[1:]:
    if st <= s:
        cnt += 1
        st = e
print(cnt)


Measured memory_bytes: 42792
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

using namespace std;

template <typename T>
static inline void ArrayInput(vector<T>& A) {
  for (auto itr = A.begin(); itr < A.end(); ++itr) cin >> *itr;
}

template <typename T>
static inline void ArrayPut(const vector<T>& A) {
  for (auto itr = A.begin(); itr < A.end(); ++itr) cout << *itr << " ";
  cout << endl;
}

bool IsPrime(uint64_t num);
int main() {
  uint64_t A, B;
  cin >> A >> B;
  set<uint64_t> Num;
  uint64_t res = 0;

  Num.insert(1);
  if (IsPrime(A)) Num.insert(A);

  if (A % 2 == 0) {
    Num.insert(2);
    if (IsPrime(A / 2)) Num.insert(A / 2);
  }
  for (uint64_t i = 3; i * i <= A; ++i) {
    if (A % i == 0) {
      if (IsPrime(i)) Num.insert(i);
      if (IsPrime(A / i)) Num.insert(A / i);
    }
  }
  for (auto itr = Num.begin(); itr != Num.end(); ++itr) {
    if (B % *itr == 0) ++res;
  }

  cout << res << endl;

  return 0;
}

bool IsPrime(uint64_t num) {
  if (num < 2)
    return false;
  else if (num == 2)
    return true;
  else if (num % 2 == 0)
    return false;
  for (uint64_t i = 3; i * i <= num; i += 2) {
    if (num % i == 0) {
      return false;
    }
  }
  return true;
}

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

class Program
{
    static void Main(string[] args)
    {
        // 入力
        long[] tmp = Console.ReadLine().Split().Select(long.Parse).ToArray();

        long h = tmp[0];
        long a = tmp[1];
        long ans = 0;
        while (h > 0)
        {
            h -= a;
            ans++;
        }

        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 13396
#include <stdio.h>

int main () {
	int h, w, n;
	int p = 0;
	scanf("%d %d %d", &h, &w, &n); 
	
	if ((n / w) < (n / h)) {
		if (n % w == 0) {
			p = n / w;
		} else {
			p = n / w + 1;
		}
	} else {
		if (n % h == 0) {
			p = n / h;
		} else {
			p = n / h + 1;
		}
	}
	printf("%d", p); 
	return 0;
}

Measured memory_bytes: 1700
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll mod=1e9+7;
int dy[]={1,-1,0,0};
int dx[]={0,0,1,-1};

ll modcombi[2001][2001]={0}; //[i][j] iCj

void makecombi(){
  modcombi[0][0]=1;
  for(int i=1;i<=2000;i++){
    modcombi[i][0]=1;
    for(int j=1;j<=2000;j++){
      modcombi[i][j]=(modcombi[i-1][j-1]+modcombi[i-1][j])%mod;
    }
  }
}


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

  //i=1
  cout<<N-K+1<<endl;

  makecombi();
  //cout<<modcombi[4][0]<<endl<<endl;
  for(int i=2;i<=K;i++){
    ll ans=(modcombi[K-1][i-1]*modcombi[N-K+1][i])%mod;
    cout<<ans<<endl;
  }

  return 0;
}



Measured memory_bytes: 31488
#pragma region noncode
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll INF = 1'010'000'000'000'000'017LL;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#pragma endregion

int main() {
    // AtCoder
    // template
    ll n, k;
    cin >> n >> k;
    vector<ll> res(n, 0);
    ll d;
    ll ans = 0;
    rep(i, k) {
        cin >> d;
        rep(j, d) {
            ll a;
            cin >> a;
            res[a - 1]++;
        }
    }

    rep(i, n) if(res[i] == 0) ans++;
    cout << ans << endl;
}


Measured memory_bytes: 3628
import sys

l, r = map(int, input().split())
ans = 10 ** 10
for i in range(l, r+1):
  for j in range(i+1, r+1):
    if (i * j) % 2019 == 0:
      print(0)
      sys.exit()
    ans = min(ans, (i*j) % 2019)
print(ans)

Measured memory_bytes: 9184
n, t = map(int, input().split())

alist = list(map(int, input().split()))

lowest = float('INF')

gain = 0

repeat = 0

for al in alist:
    if al < lowest:
        lowest = al
        continue
    else:
        if al - lowest == gain:
            repeat += 1
            continue
        if al - lowest > gain:
            gain = al - lowest
            repeat = 0
            continue

print(repeat + 1)

Measured memory_bytes: 14252
n=int(input())
h=list(map(int, input().split()))

dp=[0]*n
dp[0]=0
dp[1]=abs(h[1]-h[0])

for i in range(2,n):
    dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]))

print(dp[-1])

Measured memory_bytes: 13980
#include<bits/stdc++.h>
using namespace std;
const long long inf = 1000000000000000000;
int main() {
	int h, w;
	cin >> h >> w;
	string a[26][26];
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> a[i][j];
			if (a[i][j] == "snuke") {
				char b = 'A' + j;
				cout << b << i + 1;
				break;
			}
		}
	}
}

Measured memory_bytes: 256
#!/usr/bin/env python
# coding: utf-8
#


def main(l_):
    a, b = l_[0], l_[1]
    area = a * b
    perimeter = (a + b) * 2
    print('{} {}'.format(area, perimeter))
    
    
if '__main__' == __name__:
    try:
        while True:
            main(list(map(int,input().strip().split(' '))))
    except EOFError:
        pass



Measured memory_bytes: 5604
use std::io::prelude::*;

fn input<T: std::str::FromStr>() -> T {
    let stdin = std::io::stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}

#[allow(dead_code)]
fn with_stdout_lock<F: FnOnce(std::io::BufWriter<std::io::StdoutLock>)>(f: F) {
    let out = std::io::stdout();
    let w = std::io::BufWriter::new(out.lock());
    f(w);
}

#[allow(unused_macros)]
macro_rules! debug {
    ($var:expr) => {
        match &$var { v => eprintln!(concat!(stringify!($var), "={:?}"), v) }
    };
    ($var:expr, $($vars:expr),*) => {
        match &$var { v => eprint!(concat!(stringify!($var), "={:?} "), v) }
        debug!($($vars),*);
    };
}

fn main() {
    let n: usize = input();
    let a: Vec<i64> = (0..n).map(|_| input()).collect();

    let mut sum = vec![0; n + 1];
    for i in 0..n {
        sum[i + 1] = sum[i] + a[i];
    }

    let mut ans = i64::max_value();
    for i in 1..n - 2 {
        let lsum = sum[i + 1];
        let rsum = sum[n] - sum[i + 1];
        let lj = sum.lower_bound(&(lsum / 2));
        let rj = sum.lower_bound(&(lsum + rsum / 2));
        let (p, q) = if (sum[i + 1] - sum[lj] * 2).abs() > (sum[i + 1] - sum[lj - 1] * 2).abs() {
            (sum[lj - 1], sum[i + 1] - sum[lj - 1])
        } else {
            (sum[lj], sum[i + 1] - sum[lj])
        };
        let (r, s) = if (sum[n] - sum[rj] * 2 + sum[i + 1]).abs()
            > (sum[n] - sum[rj - 1] * 2 + sum[i + 1]).abs()
        {
            (sum[rj - 1] - sum[i + 1], sum[n] - sum[rj - 1])
        } else {
            (sum[rj] - sum[i + 1], sum[n] - sum[rj])
        };
        let mx = *[p, q, r, s].iter().max().unwrap();
        let mn = *[p, q, r, s].iter().min().unwrap();
        ans = std::cmp::min(ans, mx - mn);
    }
    println!("{}", ans);
}

trait LowerBound<T: Ord> {
    fn lower_bound_by<F: FnMut(&T) -> std::cmp::Ordering>(&self, f: F) -> usize;
    fn lower_bound(&self, x: &T) -> usize {
        self.lower_bound_by(|e| e.cmp(x))
    }
    fn lower_bound_by_key<U: Ord, F: FnMut(&T) -> U>(&self, x: &U, mut f: F) -> usize {
        self.lower_bound_by(|e| f(e).cmp(x))
    }
}
impl<T: Ord> LowerBound<T> for [T] {
    fn lower_bound_by<F: FnMut(&T) -> std::cmp::Ordering>(&self, mut f: F) -> usize {
        let mut l = -1 as i64;
        let mut r = self.len() as i64;
        while r - l > 1 {
            let m = ((l + r) / 2) as usize;
            if f(&self[m]) == std::cmp::Ordering::Less {
                l = m as i64;
            } else {
                r = m as i64;
            }
        }
        r as usize
    }
}


Measured memory_bytes: 8444
#include<stdio.h>
#include<math.h>

int main(void){
  
  int n, i = 2;
  scanf("%d", &n);
  
  while(is_prime(n) == 0){
    n++;
  }
  
  printf("%d", n);
  
  return 0;
}

int is_prime(int n){
  for(int i = 2;i <= pow(n, 0.5);i++){
      if(n % i == 0){
        return 0;
      }
    }
  return 1;
}
  

Measured memory_bytes: 384
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys

sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): #startline--------------------------------------------
    H,W = map(int,input().split())
    s = [input() for i in range(H)]
    sy,sx = 0,0
    gy,gx = H-1,W-1
    cnt = 0
    for i in range(H):
        for j in range(W):
            if s[i][j] == "#":
                cnt += 1
    inf = float("inf")
    d = [[inf]*W for i in range(H)]
    q = queue.Queue()
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    def bfs():
        for i in range(H):
            for j in range(W):
                d[i][j] = inf
        q.put([sy,sx])
        d[sy][sx]=0
        while not q.empty():
            p = q.get()
            if p[0] == gy and p[1] == gx:
                break
            for k in range(4):
                ny = p[0]+dy[k]
                nx = p[1]+dx[k]
                if 0 <= nx < W and 0 <= ny < H and s[ny][nx] != "#" and d[ny][nx] == inf:
                    q.put([ny,nx])
                    d[ny][nx] = d[p[0]][p[1]]+1
        return d[gy][gx]
    res = bfs()
    print(-1 if res == inf else H*W-cnt-res-1)
if __name__ == "__main__":
    main() #endline===============================================

Measured memory_bytes: 5432
#include <bits/stdc++.h>  // g++ -std=c++14 -o a a.cpp

using namespace std;

typedef pair<int, int> P;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define repto(i, n) for(int i = 0; i <= (n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end()) // ユニークなvectorにする。連続した値を除去して切り出す。
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
#define DEBUG(x) cout << #x << ": " << x << endl;

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

int main() {
  string s1, s2, s3;
  cin >> s1 >> s2 >> s3;
  cout << (char)toupper(s1[0])  << (char)toupper(s2[0]) << (char)toupper(s3[0]) << endl;
}


Measured memory_bytes: 256
import java.util.*;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int i = 1;
		do{
			int x = i;
			if(x%3 == 0){
				System.out.printf(" %d", i);
				continue;
			}
			do{
				if(x%10 == 3){
					System.out.printf(" %d", i);
					break;
				}
				x /= 10;
			}while(x > 0);
		}while( ++i <= n );
		System.out.printf("\n");
	}
}



Measured memory_bytes: 38856
import math
import queue
import bisect
import heapq
import time
import itertools

mod = int(1e9+7)

def swap(a,b):
    return (b,a)

def gcd(a,b): #最大公約数
    if (a<b):
        a,b = swap(a,b)
    if (b==0):
        return a
    else:
        return gcd(b,a%b)

def lcm(a,b): #最小公倍数
    return a/gcd(a,b)*b

def divisors(a): # 約数列挙
    divisors = []
    for i in range(1,int(a**0.5)+1):
        if a%i==0:
            divisors.append(i)
            if i!=a//i:
                divisors.append(a//i)
    return divisors

def is_prime(a): #素数判定
    if a<2:
        return False
    elif a==2:
        return True
    elif a%2==0:
        return False
    sqrt_num = int(a**0.5)
    for i in range(3,sqrt_num+1,2):
        if a%i==0:
            return False
    return True

def prime_num(a): #素数列挙
    pn = [2]
    for i in range(3,int(a**0.5),2):
        prime = True
        for j in pn:
            if i%j==0:
                prime = False
                break
        if prime:
            pn.append(i)
    return pn

def prime_fact(a): #素因数分解
    sqrt = math.sqrt(a)
    res = []
    i = 2
    if is_prime(a):
        res.append(a)
    else:
        while a!=1:
            while a%i==0:
                res.append(i)
                a //= i
            i += 1
    return res

def main():
    x = int(input())
    while True:
        if is_prime(x):
            print(x)
            return
        else:
            x += 1
    return

if __name__=='__main__':
    main()


Measured memory_bytes: 38636
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
#include <cassert>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>

#define cauto const auto&
#define ALL(v) begin(v),end(v)
#else
#define ALL(v) (v).begin(),(v).end()
#endif

using namespace std;


namespace{
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
	v.assign(a, vector<T>(b, t));
}
template <class T> inline T &chmin(T &x, const T &y){ return x = min(x, y); }
template <class T> inline T &chmax(T &x, const T &y){ return x = max(x, y); }
template <class F, class T>
void convert(const F &f, T &t){
	stringstream ss;
	ss << f;
	ss >> t;
}


#define REP(i,n) for(int i=0;i<int(n);++i)
#define RALL(v) (v).rbegin(),(v).rend()


#define MOD 1000000007LL
#define EPS 1e-8

size_t n;
void dfs(string s){
	if(s.size() == n){
		cout << s << '\n';
	}
	else{
		char mx = *max_element(ALL(s));
		for(char c = 'a'; c <= mx + 1; ++c){
			dfs(s + c);
		}
	}
}

void mainmain(){
	cin >> n;
	dfs("a");
}



}
int main() try{
//	ios::sync_with_stdio(false); cin.tie(0);
	cout << fixed << setprecision(10);
	cerr << fixed << setprecision(4);
	mainmain();
}
catch(...){
	throw;
}


Measured memory_bytes: 1536
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()

using namespace std;

int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, -1, 0, 1 };

int nextInt() {int a; cin >> a; return a;}
char nextChar() {char a; cin >> a; return a;}
double nextDouble() {double a; cin >> a; return a;}
string nextString() {string a; cin >> a; return a;}

template<class T> void inputVector(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < v.size(); i++) cin >> v[i];
}

int cnt[100010];

signed main() {
	int N, M;
	cin >> N >> M;

	vector<int> a(M), b(M);
	rep(i, M) {
		cin >> a[i] >> b[i];
		a[i]--; b[i]--;
		cnt[a[i]]++;
		cnt[b[i]]++;
	}

	bool ok = true;
	rep(i, 100000) {
		if (cnt[i] % 2) {
			ok = false;
			break;
		}
	}

	cout << (ok ? "YES" : "NO") << endl;

    return 0;
}


Measured memory_bytes: 2560
#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>;

int main(){
    string st, key;
    cin >> st >> key;
    int f = 0;
    if(st.size() < key.size()){
        cout << "UNRESTORABLE" << endl;
    }else if(st.size() == key.size()){
        rep(i, st.size()){
            if(st.at(i) != '?' && st.at(i) != key.at(i)){
                f = 1;
                break;
            }
        }
        if(f == 0){
            cout << key << endl;
        }else{
            cout << "UNRESTORABLE" << endl;
        }
    }else{
        vector<string> ans(0);
        rep(i, st.size()-key.size()+1){
            string a = st;
            f = 0;
            rep(j, st.size()){
                if(i <= j && j <= i+key.size()-1){
                    if(a.at(j) == '?'){
                        a.at(j) = key.at(j-i);
                    }else if(a.at(j) != key.at(j-i)){
                        f = 1;
                        break;
                    }
                }else{
                    if(a.at(j) == '?') a.at(j) = 'a';
                }
            }
            if(f == 0) ans.push_back(a);
        }
        if(ans.size() == 0){
            cout << "UNRESTORABLE" << endl;
        }else{
            sort(ans.begin(), ans.end());
            cout << ans.at(0) << endl;
        }
    }
    return 0;
}

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

const int N=200005;
vector<int> v[N];
bool vis[N];
int p[N];
int main() {
    int n, m;
    cin>>n>>m;
    for(int i=1;i<=m;i++) {
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    queue<int> q;
    q.push(1);
    while(!q.empty()){
        int y=q.front();
        q.pop();
        for(int v1:v[y]) {
            if(vis[v1]) continue;
            p[v1]=y;
            q.push(v1);
            vis[v1]=true;
        }
    }
    bool ok=true;
    for(int i=1;i<=n;i++) 
    ok&=vis[i];
    if(!ok) {
        cout<<"No"<<endl;
        return 0;
    }
cout<<"Yes"<<endl;
for(int i=2;i<=n;i++)
cout<<p[i]<<endl;
    return 0;
}


Measured memory_bytes: 12776
#include <bits/stdc++.h>
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 = m;i >= n;i--)
#define INF 1<<30
#define LINF 1LL<<62
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back
const int MOD = 1000000007;
 
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,m;cin >> n >> m;
  vector<P> v(m);
  rep(i,m){
    ll a,b;cin >>a >> b;
    a--;b--;
    v[i] = mp(b,a);
  }
  sort(all(v));
  ll ans = 0;
  ll mib = 0;
  ll maa = 0;
  rep(i,m){
    ll a = v[i].second;
    ll b = v[i].first;
    if(a>=mib){
      ans++;
      mib = b;
      maa = a;
    }else{
      maa = max(maa,a);
    }
  }
  cout << ans << endl;
  
}



Measured memory_bytes: 1792
module Main (main) where

import qualified Data.ByteString.Char8     as C8
import           Data.Maybe

main :: IO ()
main = do
  [a,b,c,d] <- readInts
  print . showAnswer $ solve (a,b,c,d)

type Input  = (Int, Int, Int, Int)
type Output = Ordering

solve :: Input -> Output
solve (a,b,c,d) = compare (a+b) (c+d)

showAnswer :: Output -> Answer
showAnswer = Compare2

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

data Answer
  = YesNo Bool
  | YESNO Bool
  | AB Bool
  | Number Int
  | Compare Ordering
  | Compare2 Ordering

instance Show Answer where
  show (YesNo b)   = if b then "Yes" else "No"
  show (YESNO b)   = if b then "YES" else "NO"
  show (AB b)      = if b then "A"   else "B"
  show (Number i)  = show i
  show (Compare o)
    | o == EQ = "="
    | o == LT = "<"
    | o == GT = ">"
  show (Compare2 o)
    | o == EQ = "Balanced"
    | o == LT = "Right"
    | o == GT = "Left"

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

int main() {
    string a,b;
    cin >> a >> b;
    int c;
    c = stoi(a+b);
    for(int i=1;i<=1000;i++){
        if(i*i==c){
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;
    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 rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
typedef long long ll;
#define ALL(v) v.begin(), v.end()
#define vmax(v) *max_element(ALL(v))
#define vmin(v) *min_element(ALL(v))
#define chmax(x, a) x = max(x, a)
#define chmin(x, a) x = min(x, a)
const ll MIN_INF = -1e18;

int main() {
    int N, M; cin >> N >> M;
    vector<ll> x(N), y(N), z(N);
    rep(i, N) cin >> x[i] >> y[i] >> z[i];
    ll ans = 0;
    rep(i, 1<<3) {
        vector<int> xyzSign(3);
        rep(j, 3) {
            xyzSign[j] = ((i & (1<<j)) ? 1 : -1);
        }
        vector<ll> vec(N);
        rep(j, N) {
            ll tmp = xyzSign[0]*x[j] + xyzSign[1]*y[j] + xyzSign[2]*z[j];
            vec[j] = tmp;
        }
        ll sum = 0;
        sort(ALL(vec));
        reverse(ALL(vec));
        rep(j, M) sum += vec[j];
        chmax(ans, sum);
    }
    cout << ans << endl;
}


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

int main(){
  int N ; 
  cin >> N ; 
  vector<int> d(N) ; 
  
  for(int i = 0 ; i < N ; i++){
    cin >> d.at(i)  ; 
  }
  
  sort(d.begin(),d.end()) ; 
  
  cout << d.at(N/2 ) - d.at(N/2 - 1) << endl ; 
  return 0 ;  
}

Measured memory_bytes: 3740
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define all(x) (x).begin(),(x).end()

using namespace std;
using ll = long long;


int main(){
    int a, b, c;
    cin >> a >> b >> c;
    if ((a == b && b != c) || (b == c && c != a) || (c == a && a != b)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}


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

ac = 0
wa = 0
tle = 0
re = 0

for i in range(N):
    j = input()
    if j == "AC":
        ac += 1
    elif j == "WA":
        wa += 1
    elif j == "TLE":
        tle += 1
    else:
        re += 1

print("AC x " + str(ac))
print("WA x " + str(wa))
print("TLE x " + str(tle))
print("RE x " + str(re))

Measured memory_bytes: 9204
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
int main(){
 ll t=1;
 //cin>>t;
 while(t--){
ll n;
cin>>n;
ll a[n];
double sum=0;
for(int i=0;i<n;i++){
    cin>>a[i];
    sum+=(1.0)/(double)a[i];
}
cout<<setprecision(20)<<(1.0)/sum<<endl;
 }
}


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

vector<int> to[101];
bool used[101];

int dfs(int v) {
	int ret = 1;
	used[v] = 1;
	for (int i=0; i<to[v].size(); ++i) {
		if ( ! used[to[v][i]]) {
			ret = max(ret, 1 + dfs(to[v][i]));
		}
	}
	used[v] = 0;
	return ret;
}

int main() {
	int n, a, b;
	while (cin >> n, n) {
		fill(to, to+101, vector<int>());
		for (int i=0; i<n; ++i) {
			cin >> a >> b;
			to[a].push_back(b);
			to[b].push_back(a);
		}
		int res = 0;
		for (int i=1; i<101; ++i) res = max(res, dfs(i));
		cout << res << endl;
	}
}

Measured memory_bytes: 1220
IDENTIFICATION DIVISION.
       PROGRAM-ID. ABC044-A.
       DATA DIVISION.
       FILE SECTION.
       WORKING-STORAGE SECTION.
       77 N PIC 9(5).
       77 K PIC 9(5).
       77 X PIC 9(5).
       77 Y PIC 9(5).
       77 ANS PIC 9(9).
       77 ANSS PIC Z(9).

       PROCEDURE DIVISION.
       MAIN-PROCEDURE.
               ACCEPT N.
               ACCEPT K FROM SYSIN.
               ACCEPT X FROM SYSIN.
               ACCEPT Y FROM SYSIN.
               IF K < N THEN
                   COMPUTE ANS = K * X + (N - K) * Y
               ELSE
                   COMPUTE ANS = N * X
               END-IF.
               MOVE ANS TO ANSS.
               DISPLAY ANSS.
               STOP RUN.
       END PROGRAM ABC044-A.


Measured memory_bytes: 636
#include <iostream>
#include<algorithm>
#include <set> 
#include <iterator> 
using namespace std;

int main() {
   int n;
   cin>>n;
   int a[n+1];
   for(int i=1;i<=n;i++)
   {
     cin>>a[i];
   }
   int dp[n+1] ;
   dp[1]=0;
   dp[0]=0;
   dp[2]=abs(a[2]-a[1]);
   for(int i=3;i<=n;i++)
   {
     dp[i]=min(dp[i-2]+abs(a[i]-a[i-2]) ,dp[i-1]+abs(a[i]-a[i-1])  ) ;
   }
   cout<<dp[n]<<endl;
	return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#include<cmath>
#include<bitset>
using namespace std;

int main(){
  int A,B;
  cin>>A>>B;
  if(A<B) cout<<0<<endl;
  else cout<<10<<endl;
}


Measured memory_bytes: 256
#include <iostream> // cin, cout, cerr
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota
#include <cstdio> // printf, scanf
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <iomanip> // cout<<setprecision(n)
#include <functional> // function<void(int)>
#include <cmath>
#include <cassert>
#include <bitset>
#include <stack>

#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...)
#endif

#define int long long // at least int64 > 9*10^18
#define EL '\n'
#define rep(i,n) for(int i = 0; i < (n); i++)
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
using Graph = std::vector<std::vector<int> >;
const int INF = 1e17;
/* libraries */

signed main() {
	int n,m,x;
	std::cin >> n >> m >> x;
	std::vector<std::vector<int> > a(n,std::vector<int>(m));
	std::vector<int> c(n);
	rep(i,n) {
		std::cin >> c[i];
		rep(j,m) {
			std::cin >> a[i][j];
		}
	}
	int min = INF;
	rep(i,1<<n) {
		int o = i;
		std::vector<int> p(m);
		int cost = 0;
		rep(j,n) {
			if(o>>j&1) {
				cost+=c[j];
				rep(k,m) p[k]+=a[j][k];
			}
		}
		int ok = true;
		rep(j,m) if(p[j]<x) ok=false;
		if(ok) min=std::min(min,cost);
	}
	if(min!=INF) print(min);
	else print(-1);
	return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#include <iostream>
#include <string>

typedef uint64_t u64;
typedef int64_t i64;
typedef uint32_t u32;
typedef int32_t i32;
typedef uint16_t u16;
typedef int16_t i16;
typedef uint8_t u8;
typedef int8_t i8;

using namespace std;

#define REP(idx, N) for (u64 idx = 0; idx < N; idx++)

int main() {
  u32 N, M, X;

  cin >> N >> M >> X;

  u32 C[N];
  u32 A[N][M];

  REP(n, N) {
    cin >> C[n];
    REP(m, M) { cin >> A[n][m]; }
  }

  vector<u32> cost;
  u32 c;
  u32 x[M];
  bool ans = false;

  REP(i, pow(2, N)) {
    memset(x, 0, sizeof(x));
    c = 0;
    REP(b, N) {
      if (i & (1 << b)) {
        REP(m, M) { x[m] += A[b][m]; }
        c += C[b];
      }
      if (all_of(&x[0], &x[M], [=](u32 x) { return x >= X; })) {
        cost.push_back(c);
      }
    }
  }

  if (cost.empty()) {
    cout << -1;
  } else {
    cout << *min_element(cost.begin(), cost.end());
  }

  return 0;
}


Measured memory_bytes: 4120
#include <iostream>
#include <queue>

using namespace std;

#define INF 1e9

int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};

struct Node {
	int x, y, dir, cost;
};

bool operator >(const Node& n1, const Node& n2) {
	return n1.cost > n2.cost;
}

int main() {
	int W, H;
	while (cin >> W >> H, W || H) {
		int op[30][30];
		for (int y = 0; y < H; ++y) {
			for (int x = 0; x < W; ++x) {
				cin >> op[y][x];
			}
		}
		int c[4];
		for (int i = 0; i < 4; ++i) cin >> c[i];

		int ans = INF;
		bool gone[30][30][4] = {0};
		priority_queue<Node, vector<Node>, greater<Node> > Q; Q.push( (Node){0, 0, 1, 0} );
		while ( !Q.empty() ) {
			Node node = Q.top(); Q.pop();
			int x = node.x, y = node.y, dir = node.dir, cost = node.cost;
			if (x < 0 || x >= W || y < 0 || y >= H) continue;

			if (gone[y][x][dir]) continue;
			gone[y][x][dir] = true;

			if (x == W-1 && y == H-1) {
				ans = min(ans, cost);
			}

			for (int i = 0; i < 4; ++i) {
				int d = (dir + i) % 4;
				Q.push( (Node){x+dx[d], y+dy[d], d, cost+c[i]} );
			}
			if (op[y][x] != 4) {
				int d = (dir + op[y][x]) % 4;
				Q.push( (Node){x+dx[d], y+dy[d], d, cost} );
			}
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 1608
import Data.List

f _ [] = []
f m ([d,p]:r) =
  if m >= d
  then f (m-d) r
  else [d-m,p]:r

ans' m dp =
  let s = f m $ sortBy (\[d0,p0] [d1,p1] -> compare p1 p0) dp
      a = foldr (\[d,p] a -> a + d*p) 0 s
  in
    a

ans ([0,0]:_) = []
ans ([n,m]:l) =
  let dp = take n l
      r  = drop n l
      a  = ans' m dp
  in
    a:(ans r)

main = do
  c <- getContents
  let i = map (map read) $ map words $ lines c :: [[Int]]
      o = ans i
  mapM_ print o



Measured memory_bytes: 10148
#include <bits/stdc++.h>
#include <map>
using namespace std;
int caonima;
map<string,int> m;
long long nb(long long);

long long v[500005];

int main()
{
	int a;
	cin >> a;
    for(int i = 0; i < a; i++){
    	string str;
    	cin >> str;
    	sort(str.begin(),str.end());
    	m[str]++;
//    	cout << m[str];
	}
//	cout << m[str];
	long long b = 0;
	map<string,int>::iterator it;
    for(it = m.begin(); it != m.end(); it++){
    	b += nb(it->second);
	}
	cout << b;
	return 0;
}
long long nb(long long n)
{
	if(!v[n]) {
		long long t = n * (n - 1) / 2;
		v[n] = t;
		return t;
	}else{
		return v[n];
	}

}


Measured memory_bytes: 11136
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,no-stack-protector,fast-math")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define IO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
const int N = 4e5 + 5, M = 2 * N + 5;

int n, a[N];
map<int, int> cnt;

int main(){
    scanf("%d", &n);
    for(int i = 0 ; i < n ; ++i){
        scanf("%d", a + i);
        ++cnt[i - a[i]];
    }
    ll ans = 0;
    for(int i = 0 ; i < n ; ++i){
        --cnt[i - a[i]];
        int nw = i + a[i];
        if(nw < n)
            ans += cnt[nw];
    }
    printf("%lld\n", ans);
}

Measured memory_bytes: 14800
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <iomanip>
#include <queue>
#include <map>
#include <set>
#include <random>
#include <sstream>
#include <stack>
#include <deque>

using namespace std;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

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

int H, W, D;

int main() {
  cin >> H >> W >> D;
  map<int,pii> mp;
  rep(i,H) rep(j,W) {
    int a;
    cin >> a;
    mp[a] = pii(i, j);
  }
  int c[H*W+1] = {};
  REP(i,1,D+1) {
    for (int j = i; j < H*W+1; j += D) {
      if (j > i) {
        int y1 = mp[j-D].first;
        int x1 = mp[j-D].second;
        int y2 = mp[j].first;
        int x2 = mp[j].second;
        c[j] += c[j-D] + abs(x1 - x2) + abs(y1 - y2);
      }
    }
  }
  int Q;
  cin >> Q;
  rep(i,Q) {
    int l, r;
    cin >> l >> r;
    cout << c[r] - c[l] << endl;
  }
  return 0;
}


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

#define rep(i,n) for(int i=0;i<(n);++i)

int main()
{
    string s,t; cin >> s >> t;
    int sLen=s.length();
    int tLen=t.length();

    int max_match=0;
    for (int i=0;i<=sLen-tLen;++i){
        int match=0;
        for (int j=0;j<tLen;++j){
            if (s[i+j]==t[j]) ++match;
        }
        max_match=max(max_match,match);
    }
    cout << tLen-max_match << endl;
    return 0;
}


Measured memory_bytes: 3624
#include<stdio.h>
int main(){
	int a,b;
	while(scanf("%d",&a),a){
		scanf("%d",&b);
		for(int i=0;i<b;i++){
			int c,d;
			scanf("%d%d",&c,&d);
			a-=d-c;
		}
		if(a<=0)printf("OK\n");
		else printf("%d\n",a);
	}
}

Measured memory_bytes: 1040