akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
using namespace std;
using ll = long long;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<int> S(n);
  REP(i, n) cin >> S[i];

  int q;
  cin >> q;
  vector<int> T(q);
  REP(i, q) cin >> T[i];

  int ans = 0;

  for(int i = 0; i < q; i++) {
    int key = T[i];
    int left = 0;
    int right = n;
    while(left < right) {
      int mid = (left + right) / 2;
      if(S[mid] == key) {
        ans++;
        break;
      } else if(S[mid] > key) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
  }

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


Measured memory_bytes: 3320
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); i++)
using namespace std;
 
int g[15][15];
int main () {
  int n;
  cin >> n;
  rep(i,n)rep(j,n) g[i][j] = -1;
  rep(i,n){
    int a;
    cin >> a;
    rep(j,a){
      int x, y;
      cin >> x >> y;
      x--;
      g[i][x] = y;
    }
  }
  int ans = 0;
  rep(i,1<<n){
    vector<int> d(n);
    rep(j,n) if(i>>j&1){
      d[j] = 1;
    }
    bool ok = true;
    rep(j,n){
      if(d[j]){
        rep(k,n){
          if(g[j][k] == -1) continue;
          if(g[j][k] != d[k]) ok = false;
        }
      }
    }
    if(ok) ans = max(ans, __builtin_popcount(i));
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define r(i,b) for(int i=0;i<b;i++)
main(){
  int n;
  cin>>n;
  string s;
  cin>>s;
  vector<int>v;
  r(i,s.size()){
    if(i!=s.size()-1&&s[i]==s[i+1]){
      v.push_back(2);
      i++;
    }
    else v.push_back(1);
  }
  int dp[100];
  if(v[0]==2)dp[0]=6;
  else dp[0]=3;
  for(int i=1;i<v.size();i++){
    if(v[i-1]==1&&v[i]==1)dp[i]=dp[i-1]*2;
    if(v[i-1]==1&&v[i]==2)dp[i]=dp[i-1]*2;
    if(v[i-1]==2&&v[i]==1)dp[i]=dp[i-1];
    if(v[i-1]==2&&v[i]==2)dp[i]=dp[i-1]*3;
    dp[i]%=1000000007;
  }
  cout<<dp[v.size()-1]<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <numeric>

using namespace std;
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

typedef long long ll;

long long GCD(long long a, long long b){if(b==0)return a;return GCD(b,a%b);}

int main() {
    int N; cin >> N;
    ll K; cin >> K;
    int Q; cin >> Q;
    vector<int> A(Q);
    repp(i,0,Q) cin >> A[i];

    vector<ll> point(N+1);
    repp(i,0,Q) point[A[i]] += 1;

    repp(i,1,N+1) {
        if (K-(Q - point[i]) > 0)  cout << "Yes"  << endl;
        else cout << "No" << endl;
    }
}


Measured memory_bytes: 1792
{-# LANGUAGE Strict #-}
import           Data.Char (isDigit)

main :: IO ()
main = do
  [a, b] <- map read . words <$> getLine
  s <- getLine
  putStrLn $ if solve a b s then "Yes" else "No"

solve :: Int -> Int -> String -> Bool
solve a _ s = all isDigit xs && y == '-' && all isDigit ys
  where (xs, y:ys) = splitAt a s


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

#define PI 3.14159265359
#define rep(i,a,n) for(int i=a;i<(int)n;++i)
#define SZ(x) ((int)(x).size())	//size() unsigned -> int
#define descSort(a) sort(a.begin(),a.end(),std::greater<int>())
using namespace std;
typedef long long ll;
const ll INF = 1e9 + 7;

int main() {
    int n;
    cin>>n;
    int ma=0,ans;
    rep(i,0,n){
        int a,b;
        cin>>a>>b;
        if(ma < a){
            ma = a;
            ans=a+b;
        }
    }

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

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < n; ++i)
using ll = long long;
const ll MOD = 1000000007;//998244353;
char A[300][300];
int ans[300][300];
int id = 0;
void rec(int u,int d,int l,int r) {
    bool flag = false;//trueなら横falseなら縦に切る
    int cnt=0;
    for (int i=u;i<d;i++){
        for (int j=l;j<r;j++){
            if (A[i][j]=='#'){
                cnt++;
                if(cnt >= 2){
                    if(flag){
                        rec(u,i,l,r);
                        rec(i,d,l,r);
                    }
                    else{
                        rec(u,d,l,j);
                        rec(u,d,j,r);
                    }
                    return;
                }
            }
        }
        if(cnt==1)flag = true;
    }
    if (cnt==1){
        id++;
        for (int i=u;i<d;i++){
            for (int j=l;j<r;j++){
                ans[i][j]=id;
            }
        }
    }
}
void solve() {
   int h,w,k; cin >> h >> w >> k;
   rep(i,h){
       string s; cin >> s;
       rep(j,w){
           A[i][j] = s[j];
       }
   }
   rec(0,h,0,w);
   rep(i,h){
       rep(j,w){
           cout << ans[i][j] << " ";
       }
       cout << endl;
   }
}
int main() {
   cin.tie(nullptr); ios::sync_with_stdio(false);
   solve();
}

Measured memory_bytes: 1280
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <stack>
#include <cmath>
#define ll long long
#define LINF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
#define PI 3.14159265
using namespace std;
const int MAX = 1e5 + 10;
const ll MOD = 1e9 + 7;
int N, M, K, Q, L;
int jump[MAX][33];
int A[MAX];

int func(int i, int j) {
	if (j == 0) return jump[i][j];
	int &ret = jump[i][j];
	if (ret != -1) return ret;
	return ret = func(func(i, j - 1), j - 1);
}


int main()
{
	int i, j, k, a, b;
	scanf("%d", &N);
	memset(jump, -1, sizeof(jump));
	for (i = 1; i <= N; ++i) scanf("%d", A + i);
	scanf("%d%d", &L, &Q);
	for (i = 1; i <= N; ++i) {
		auto it = upper_bound(A + 1, A + 1 + N, A[i] + L);
		it--;
		jump[i][0] = it - A;
	}
	j = 0;
	while ((N >> j) > 1) j++;
	for (i = 1; i <= N; ++i) func(i, j);
	for (i = 1; i <= Q; ++i) {
		scanf("%d%d", &a, &b);
		int days = 0;
		if (a > b) swap(a, b);
		for (k = j; k >= 0; --k) {
			if (jump[a][k] < b) {
				a = jump[a][k];
				days += (1 << k);
			}
		}
		printf("%d\n", days + 1);
	}


}

Measured memory_bytes: 14080
#include <iostream>
#include <iomanip>
#include<algorithm>
#include <map>
#include <vector>
#include <string>
#include <tuple>
#include <set>
#include <queue>

using namespace std;

using T=tuple<int, int>;

class Solver {
};
	int main() {
		while (true) {
			int n, w, d;
			cin >> n >> w >> d;
			if (w == 0)break;

			map<int, T> dict;
			dict.emplace(1, make_tuple(w, d));
			for (int i = 0; i < n; i++) {
				int p, s;
				cin >> p >> s;
				map<int, T> next;
				int j = 1;
				for (auto itr : dict) {
					if (itr.first == p)continue;
					next.emplace(j, itr.second);
					j++;
				}
				int ww = get<0>(dict[p]);
				int dd = get<1>(dict[p]);
				s %= (ww + dd);
				if (s < ww) {
					if (s <= ww / 2) {
						next.emplace(j, make_tuple(s, dd));
						next.emplace(j+1, make_tuple(ww-s, dd));
					}
					else {
						next.emplace(j, make_tuple(ww - s, dd));
						next.emplace(j + 1, make_tuple(s, dd));
					}
				}
				else {
					s -= ww;
					if (s <= dd / 2) {
						next.emplace(j, make_tuple(ww, s));
						next.emplace(j + 1, make_tuple(ww, dd - s));
					}
					else {
						next.emplace(j, make_tuple(ww, dd - s));
						next.emplace(j + 1, make_tuple(ww, s));
					}
				}
				dict = next;
			}

			vector<int> rects;
			for (auto itr : dict) {
				rects.emplace_back(get<0>(itr.second) * get<1>(itr.second));
			}

			sort(rects.begin(), rects.end());
			for (int i = 0; i < rects.size(); i++) {
				cout << rects[i];
				if (i < rects.size() - 1)cout << ' ';
			}
			cout << endl;
		}
	}


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

public class Main {

	public static void main(String[] args) throws Exception {
		FastScanner sc = new FastScanner(System.in);
		PrintWriter out = new PrintWriter(System.out);

		solve(sc,out);

		out.flush();
	}

	public static void solve(FastScanner sc, PrintWriter out) {
		int p = sc.nextInt();
		int q = sc.nextInt();
		int r = sc.nextInt();
		
		int min = Integer.MAX_VALUE;
		
		min = Math.min(min, p+q);
		min = Math.min(min, r+q);
		min = Math.min(min, p+r);
		min = Math.min(min, q+r);
		min = Math.min(min, r+p);
		min = Math.min(min, p+q);
		out.println(min);
	}

	public static int gcd(int a, int b) {
		if(a < b) return gcd(b, a);
		if(b == 0) return a;
		return gcd(b, a % b);
	}

	public static long gcd(long a, long b) {
		if(a < b) return gcd(b, a);
		if(b == 0) return a;
		return gcd(b, a % b);
	}

	public static int lcm(int a, int b) {
		return a / gcd(a, b) * b;
	}

	public static long lcm(long a, long b) {
		return a / gcd(a, b) * b;
	}
}

class Pair<K, V> extends AbstractMap.SimpleEntry<K, V> {

    public Pair(K key, V value) {
        super(key, value);
    }

    public Pair<V, K> swap() {
    	return new Pair<V, K>(getValue(), getKey());
    }
 }

class FastScanner {
    private BufferedReader reader = null;
    private StringTokenizer tokenizer = null;

    public FastScanner(InputStream in) {
        reader = new BufferedReader(new InputStreamReader(in));
        tokenizer = null;
    }

    public String next() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public String nextLine() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        return tokenizer.nextToken("\n");
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public double nextDouble() {
         return Double.parseDouble(next());
     }

    public int[] nextIntArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = nextInt();
        return a;
    }

    public long[] nextLongArray(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++)
            a[i] = nextLong();
        return a;
    }
}

Measured memory_bytes: 22740
#include <bits/stdc++.h>
#include<algorithm>
#define int long long
using namespace std;
typedef pair<int,int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1000000000000

int MOD=1000000007;
int modpow(int a,int x){
  if(a<0)a+=MOD;
  int ans=1;
  while(x>0){
    if(x&1) ans=ans*a%MOD;
      a=a*a%MOD;
      x>>=1;
  }
  return ans;
}

int gyaku(int n){
    return modpow(n,MOD-2);
}

auto factor(int n){
  map<int,int>res;
  for(int i=2;i*i<=n;i++){
      for(; n%i==0;n/=i) res[i]++;
  }
  if(n>1)res[n]++;
  return res;
}
////////////////////////////////////////////////////////////
signed main() {
  int n,a,b;
  cin>>n>>a>>b;
  vector<int>v(n);
  rep(i,n)cin>>v[i];
  int ans=0;
  rep(i,n-1){
    if(a*(v[i+1]-v[i])>b)ans+=b;
    else ans+=a*(v[i+1]-v[i]);
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 3952
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)n; i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long int ll;
typedef vector<int > vecint;
typedef vector<bool > vecbool;
typedef vector<string > vecstr;
typedef vector<vector<int > > vec2int;
typedef vector<vector<bool > > vec2bool;
int dx[4] {-1,+1, 0, 0};
int dy[4] { 0, 0,-1,+1};
int main()
{
  int n, m;
  cin >> n >> m;
  vector<list<int> > a(n);
  int x, y;
  REP(i,m){
    cin >> x >> y;
    a[x - 1].push_back(y - 1);
    a[y - 1].push_back(x - 1);
  }
  //////////////////////////////
  // REP(i,n){
  //   cout << i << ", ";
  //   for(auto itr = a[i].begin(); itr != a[i].end(); itr++){
  //     cout << *itr << " ";
  //   }
  //   cout << endl;
  // }
  //////////////////////////////
  vecint arr(n - 1,0);
  REP(i,n - 1){
    arr[i] = i + 1;
  }
  //////////////////////////////
  int ans = 0;
  bool ok;
  do{
    ok = true;
    int x = 0;
    int y;
    REP(i,n-1){
      y = arr[i];
      if(count(all(a[x]),y) == 0){
	ok = false;
	break;
      }
      x = y;
    }
    if(ok){
      // REP(i,n - 1){
      // 	cout << setw(2) <<arr[i];
      // }
      // cout << endl;
      ans++;
    }
  }while(next_permutation(all(arr)));
  cout << ans << endl;

}


Measured memory_bytes: 256
s = '1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51'.split(', ')
k = gets.to_i - 1
puts s[k]

Measured memory_bytes: 3836
# include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1000;
int a[N], b[N];
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	for(int i = 1; i <= n; i ++){
		cin >> a[i];
		b[i] = i; 
	}
	int j = 1, ans = 0;
	for(int i = 1; i <= n; i ++){
		while(j <= n && a[j] != b[i]) j ++;
		if(a[j] == b[i])ans ++;
		else break;
	}
	if(!ans) ans = n + 1;
	cout << n - ans << '\n';
}

Measured memory_bytes: 1792
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <limits>
#include <fstream>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int queen[8][8]; // 0,1(最初から置いてある),2(置いてある)
bool check(int h, int w){
  FOR(i,0,8){
    if(queen[h][i]!=0){
      return false;
    }
  }
  FOR(i,0,8){
    if(queen[i][w]!=0){
      return false;
    }
  }
  FOR(i,0,8){
    int hh = h + i;
    int ww = w + i;
    if(hh < 0 || hh >= 8 || ww < 0 || ww >= 8) break;
    if(queen[hh][ww]!=0){
      return false;
    }
  }
  FOR(i,0,8){
    int hh = h - i;
    int ww = w - i;
    if(hh < 0 || hh >= 8 || ww < 0 || ww >= 8) break;
    if(queen[hh][ww]!=0){
      return false;
    }
  }
  FOR(i,0,8){
    int hh = h + i;
    int ww = w - i;
    if(hh < 0 || hh >= 8 || ww < 0 || ww >= 8) break;
    if(queen[hh][ww]!=0){
      return false;
    }
  }
  FOR(i,0,8){
    int hh = h - i;
    int ww = w + i;
    if(hh < 0 || hh >= 8 || ww < 0 || ww >= 8) break;
    if(queen[hh][ww]!=0){
      return false;
    }
  }
  return true;
}
void rec(int gyou){
  if(gyou==8){
    FOR(i,0,8){
      FOR(j,0,8){
        cout<<(queen[i][j]==0?'.':'Q');
      }
      cout<<endl;
    }
    exit(0);
  }
  FOR(i,0,8){
    if(check(gyou, i)||queen[gyou][i]==1){
      if(queen[gyou][i]==0) queen[gyou][i] = 2;
      rec(gyou + 1);
      if(queen[gyou][i]==2) queen[gyou][i] = 0;
    }
  }
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n; cin >> n;
  FOR(i,0,n){
    int y, x;
    cin >> y >> x;
    queen[y][x] = 1;
  }
  rec(0);
}


Measured memory_bytes: 3196
n = int(input())

a = []
x = [[] for _ in range(n)]

for i in range(n):
    
    k = int(input())
    a.append(k)
    
    for j in range(k):
        x[i].append(list(map(int,input().split())))

# print(x)
ans = 0
for i in range(1<<n):
    
    cnt = bin(i).count("1")
    if ans > cnt:
        continue
    flag = True
    for j in range(n):
        # if i==3:
        #     print(i,j,i>>j&1,cnt)
        if i>>j & 1:
            # True if 1
            # if i==3:
                # print(i,j)
            for t in x[j]:
                # 証言:testimony
                # if i == 3:
                    # print(i,t[0]-1, i>>t[0]-1, t[1])
                if (i>>(t[0]-1) &1 ) != t[1]:
                    flag = False
                    break
        if flag == False:
            break
    if flag == True:
        # print(i) # 0 000
        ans = cnt

print(ans)


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

using namespace std;

#define Rep(i,a,b) for(ll i = a; i < b; ++i)
#define rep(i,b) Rep(i,0,b)
#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;

using pint = std::pair<int, int>;
using pll = std::pair<ll, ll>;

constexpr int inf = 1e9 + 7;
constexpr ll infll = 1ll << 60ll;
constexpr ll mod = 1e9 + 7;
// 0~3までは右左下上 4~7までは斜め
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

namespace {
    template<typename T> void chmax(T& a, T b) { a = std::max(a, b); }
    template<typename T> void chmin(T& a, T b) { a = std::min(a, b); }
    template<typename T> void chadd(T& a, T b) { a = a + b; }

    void Cout(long long x, const char* end = "\n") { std::cout << x << end; }
    template <typename T> void Cout(const T& x, const char* end = "\n") { std::cout << x << end; }
    template <typename T> void Cout(const std::vector<T>& x, const char* sep = " ", const char* end = "\n") { for (std::size_t i = 0, sz = x.size(); i < sz; i++) { std::cout << x[i] << (i == sz - 1 ? end : sep); } }

    // 標準入出力
    struct inp {
        std::size_t sz;
        inp(std::size_t _sz = 1) : sz(_sz) {}
        template <typename T> operator T () const { T a; std::cin >> a; return a; }
        template <typename T> operator std::vector<T>() const { vector<T> a(sz); for (std::size_t i = 0; i < sz; i++) std::cin >> a[i]; return a; }
        template <typename T, typename U> operator std::pair<T, U>() const { T f; U s; std::cin >> f >> s; return std::pair<T, U>(f, s); }
    };

    inp inp1; // input one
}

int main() {

    string n = inp1;

    bool yes = false;
    rep(i, n.size()) {
        if (n[i] == '7') yes = true;
    }

    Cout(Yes(yes));

    return 0;
}


Measured memory_bytes: 3596
N = int(input())
XY = [tuple([int(_) for _ in input().split()]) for i in range(N)]

if N == 1:

    result = 1

else:

    XY.sort()

    dxy = [
        (XY[i][0] - XY[j][0], XY[i][1] - XY[j][1])
        for i in range(N)
        for j in range(i + 1, N)
    ]

    from collections import Counter

    cdxy = Counter(dxy)

    m = max(cdxy.values())

    #print(XY)
    #print(dxy)
    #print(cdxy)

    result = N - m

print(result)


Measured memory_bytes: 39152
#include <algorithm>  
#include <climits>
using namespace std;  

#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
typedef long long ll;

const int MAXN=300000;

typedef struct L { ll a,b; L() {} L(ll a,ll b):a(a),b(b) {} } L;
typedef struct Hull {
	L l[MAXN]; int nl;
	void clear() { nl=0; }
	bool ok(const L &p,const L &q,const L &r) {	return (q.b-p.b)*(p.a-r.a)>(r.b-p.b)*(p.a-q.a);	}
	ll get(const L &p,int x) { return p.a*x+p.b; }
	void add(int idx,ll sum,ll have) {
		L cur(-idx,(ll)idx*(idx-3)/2+sum+have);
		while(nl>=2&&!ok(l[nl-2],l[nl-1],cur)) --nl;
		l[nl++]=cur;
	}
	ll query(int idx,ll sum) {
		while(nl>=2&&get(l[nl-2],idx)>=get(l[nl-1],idx)) --nl;
		ll ret=get(l[nl-1],idx)+(ll)(idx+1)*(idx+2)/2-sum;
		return ret;
	}
} Hull;
Hull h;

int n,nq;
int cost[MAXN]; ll pcost[MAXN],scost[MAXN];
ll mxlft[MAXN];
ll mxrgt[MAXN];
ll mxwth[MAXN];
ll tmp[MAXN];

void dconq(int l,int r) {
	int m=l+(r-l)/2;
	h.clear(); FORE(i,l,m) h.add(i,pcost[i],mxlft[i]); FORE(i,m,r) tmp[i]=h.query(i,pcost[i]+cost[i])+mxrgt[i];
	for(int i=r-1;i>=m;--i) tmp[i]=max(tmp[i+1],tmp[i]); FORE(i,m,r) mxwth[i]=max(mxwth[i],tmp[i]);
	h.clear(); for(int i=r;i>=m;--i) h.add(n-i-1,scost[i],mxrgt[i]); for(int i=m-1;i>=l;--i) tmp[i]=h.query(n-i-1,scost[i]+cost[i])+mxlft[i];
	FOR(i,l+1,m) tmp[i]=max(tmp[i-1],tmp[i]); FOR(i,l,m) mxwth[i]=max(mxwth[i],tmp[i]);
	if(l<=m-1) dconq(l,m-1);
	if(m+1<=r) dconq(m+1,r);
}

void precalc() {
	pcost[0]=0; REP(i,n-1) pcost[i+1]=pcost[i]+cost[i];
	scost[n-1]=0; for(int i=n-1;i>=1;--i) scost[i-1]=scost[i]+cost[i];
	h.clear(); mxlft[0]=0;
	REP(i,n-1) { h.add(i,pcost[i],mxlft[i]); mxlft[i+1]=max(mxlft[i],h.query(i,pcost[i]+cost[i])); }
	h.clear(); mxrgt[n-1]=0;
	for(int i=n-1;i>=1;--i) { h.add(n-i-1,scost[i],mxrgt[i]); mxrgt[i-1]=max(mxrgt[i],h.query(n-i-1,scost[i]+cost[i])); }
	REP(i,n) mxwth[i]=LLONG_MIN;
	dconq(0,n-1);
}

void run() {
	scanf("%d",&n); REP(i,n) scanf("%d",&cost[i]);
	precalc();
	scanf("%d",&nq);
	REP(i,nq) {
		int idx,ncost; scanf("%d%d",&idx,&ncost); --idx;
		ll res=max(mxlft[idx]+mxrgt[idx],mxwth[idx]+cost[idx]-ncost);
		printf("%lld\n",res);
	}
}

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


Measured memory_bytes: 17792
#include <stdio.h>
int main(void){
    // Your code here!
         int h,w,i,j;
          while(1){
          scanf("%d %d",&h,&w);
           if( h==0 && w==0)
              break;
           for(i=1; i<=h; i++){
            for(j=1; j<=w; j++){
              if(i==1 || i==h || j==1 || j==w)
              printf("#");
             else
              printf(".");
             }printf("\n");
            }printf("\n");
           }
            return 0;
    }


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

using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(int i=n; i>-1; --i)
#define ALL(a) (a).begin(),(a).end()
#define FILL(a,n,x); REP(i,(n)){ (a)[i]=(x); }
#define CINA(a,n); REP(i,(n)){ cin >> (a)[i]; }
#define FILL2(a,n,m,x); REP(i,(n)){ REP(j,(m)){(a)[i][j]=(x);} }
#define CINA2(a,n,m); REP(i,(n)){ REP(j,(m)){cin >> (a)[i][j];} }
#define Liny "Yes\n"
#define Linn "No\n"
#define LINY "YES\n"
#define LINN "NO\n"

#define umap unordered_map
//cout << setfill('0') << right << setw(4) << 12; // "0012"
int keta(ll x){ if(x<10){return 1;} else{return keta(x/10) + 1;}}
int keta_wa(ll x){ if(x<10){return x;} else{return keta_wa(x/10) + x%10;} }
int ctoi(char c){ return ( (c>='0' && c<='9')? c - '0': 0 );}
int __stoi(string s){ return atoi(s.c_str()); }
ll sum(ll a[],ll N){ return accumulate(a,a+N,0LL);}
ll gcd(ll a,ll b){if(a<b)swap(a,b); return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){if(a<b){swap(a,b);} return a/gcd(a,b)*b;}
template<class T> void chmax(T& a, T b){ if(a<b){a=b;} }
template<class T> void chmin(T& a, T b){ if(a>b){a=b;} }


struct kumi{
    ll a,b,c,d;
};



int main(){
    ll N,M,Q;
    cin >>N>>M>>Q;
    kumi k[Q];
    REP(i,Q){
        ll a,b,c,d; cin>>a>>b>>c>>d;
        k[i].a = a;
        k[i].b = b;
        k[i].c = c;
        k[i].d = d;
    }
    
    ll ans = 0;
    
    int a[11];
    a[1] = 1;
    int a2,a3,a4,a5,a6,a7,a8,a9,a10;
    for(a2=1;a2<=M;++a2){
        a[2] = a2;
        for(a3=a2;a3<=M;++a3){
            a[3] = a3;
            for(a4=a3;a4<=M;++a4){
                a[4] = a4;
                for(a5=a4;a5<=M;++a5){
                    a[5] = a5;
                    for(a6=a5;a6<=M;++a6){
                        a[6] = a6;
                        for(a7=a6;a7<=M;++a7){
                            a[7] = a7;
                            for(a8=a7;a8<=M;++a8){
                                a[8] = a8;
                                for(a9=a8;a9<=M;++a9){
                                    a[9] = a9;
                                    for(a10=a9;a10<=M;++a10){
                                        a[10] = a10;
                                        ll temp = 0;
                                        REP(i,Q){
                                            kumi x = k[i];
                                            if( a[x.b] - a[x.a] == x.c){ temp += x.d;}
                                        }
                                        chmax(ans,temp);
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    
    
    cout << ans <<"\n";
    
    
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,t) for(int i=s;i<t;i++)
typedef long long ll;
#define pii pair<ll,ll>
#define mid (l+r)/2
#define lnode now * 2
#define rnode now * 2 + 1
#define MAXNUM 222222
ll tree[MAXNUM*4];ll sum[MAXNUM*4],num[MAXNUM],add[MAXNUM*4];
int allx[MAXNUM],xsize;
void pushit(int now,int num)
{
    add[now]+=num,tree[now]+=sum[now]*num;
}
void pushdown(int now)
{
    if(add[now])
        pushit(lnode,add[now]),pushit(rnode,add[now]),add[now]=0;
}
void change(int now,int l,int r,int ql,int qr,ll num)
{
    if(l==ql&&r==qr){pushit(now,num);return;}
    pushdown(now);
    if(qr<=mid)change(lnode,l,mid,ql,qr,num);
    else if(ql>mid)change(rnode,mid+1,r,ql,qr,num);
    else change(lnode,l,mid,ql,mid,num),change(rnode,mid+1,r,mid+1,qr,num);
    tree[now]=tree[lnode]+tree[rnode];
}
ll query(int now,int l,int r,int pos)
{
    if(l==r)return tree[now];
    pushdown(now);
    if(pos<=mid)return query(lnode,l,mid,pos);
    else return tree[lnode]+query(rnode,mid+1,r,pos);
}
void create(int now,int l,int r)
{
    if(l==r)
    {
        sum[now]=num[l];return;
    }
    create(lnode,l,mid),create(rnode,mid+1,r);
    sum[now]=sum[lnode]+sum[rnode];
}
const ll inf=1e18;
pii allq[MAXNUM];
int main()
{
    ll allb=0;
    int q,a,b;scanf("%d",&q);
    rep(i,1,q+1)
    {
        scanf("%d",&a);
        if(a==1)
        {
            scanf("%d%d",&a,&b);
            allq[i] = {a, b};
            allx[++xsize] = a;
        }
        else allq[i]={inf,inf};
    }
    sort(allx+1,allx+xsize+1);
    xsize=unique(allx+1,allx+xsize+1)-allx-1;
    rep(i,2,xsize+1)num[i]=allx[i]-allx[i-1];
    create(1,1,xsize);
    rep(i,1,q+1)
    {
        if(allq[i].first!=inf)
        {
            allb += (allq[i].first - allx[1]) + allq[i].second;
            allq[i].first = lower_bound(allx + 1, allx + xsize + 1, allq[i].first) - allx;
            change(1, 1, xsize, 1, allq[i].first, -1);
            if (allq[i].first != xsize)
                change(1, 1, xsize, allq[i].first + 1, xsize, 1);
        }
        else {
            ll l = 1, r = xsize-1, res = xsize;
            while (l <= r)
            {
                if (query(1, 1, xsize, mid) <= query(1, 1, xsize, mid + 1))res=mid,r=mid-1;
                else l=mid+1;
            }
            printf("%d %lld\n", allx[res],allb + query(1, 1, xsize, res));
        }
    }
}


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

int A, B;

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

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

using namespace std;

using ll = long long;
struct Edge {
    int dst;
    ll w;
    Edge() {}
    Edge(ll d, ll w) : dst(d), w(w) {}
};
using Graph = vector<vector<Edge>>;
struct Cube { ll p[3]; };

// グラフを構成する
Graph MakeGraph(const int n, const int s, vector<Cube> &c) {
    Graph g(n);
    ll d[3];

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            for (int k = 0; k < 3; ++k)
                d[k] = s - abs(c[i].p[k] - c[j].p[k]);

            // c[i]とc[j]は交差しない
            if (min({d[0], d[1], d[2]}) <= 0) continue;

            ll w = 2 * d[0] * d[1] + 2 * d[0] * d[2] + 2 * d[1] * d[2];
            g[i].emplace_back(Edge(j, w));
            g[j].emplace_back(Edge(i, w));
        }
    }

    return g;
}

ll Dfs(const int start, const int prev, const int cur, int size, const Graph &g) {
    if (size == 0) {
        if ((g[cur].size() == 2) && ((g[cur][0].dst == start && g[cur][0].dst != prev)
             || (g[cur][1].dst == start && g[cur][1].dst != prev)))
            return (g[cur][0].dst == start) ? g[cur][0].w : g[cur][1].w;
        else
            return 0;
    }

    ll max_w = -1;
    for (const auto &e : g[cur])
        if (e.dst != prev) {
            const ll res = Dfs(start, cur, e.dst, size - 1, g);
            if (res != -1) max_w = max(max_w, res + e.w);
        }

    return max_w;
}

int MinimumArea(const int n, const int k, const int s, const Graph &g) {
    ll res = -1;

    for (int v = 0; v < n; ++v)
        res = max(res, Dfs(v, -1, v, k - 1, g));

    return (res == -1) ? -1 : 6 * k * s * s - res;
}

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

    int n, k, s;

    while (cin >> n >> k >> s, n) {
        vector<Cube> cube(n);
        for (auto &c : cube)
            for (int i = 0; i < 3; ++i) cin >> c.p[i];

        cout << MinimumArea(n, k, s, MakeGraph(n, s, cube)) << '\n';
    }

    return 0;
}



Measured memory_bytes: 3212
//01-bfs
//ノーコストの手段で移動する
//何らかのコストや回数制限のある手段で移動する
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

int main(){
    long long h, w;
    cin >> h >> w;
    long long sh, sw, gh, gw;
    cin >> sh >> sw >> gh >> gw;
    sh--, sw--, gh--, gw--;

    char maze[h][w];

    for(long long i = 0; i < h; i++){
        for(long long j = 0; j < w; j++){
            cin >> maze[i][j];
        }
    }

    vector<vector<long long> > cost(h, vector<long long>(w, 1e12));//今回は距離でなくコストなので,-1ではなく無限

    cost[sh][sw] = 0;
    deque<pair<long long, long long> > q;//01-bfsはdequeを使用 前後からpush, popができる 

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

    q.push_front(make_pair(sh, sw));

    while(!q.empty()){
        pair<long long, long long> top;
        top = q.front();
        q.pop_front();
        
        //普通の移動 cost 0
        for(long long i = 0; i < 4; i++){
            if(0 <= top.first+dy[i] and top.first+dy[i] < h and 0 <= top.second+dx[i] and top.second+dx[i] < w and maze[top.first+dy[i]][top.second+dx[i]] == '.' and cost[top.first+dy[i]][top.second+dx[i]] > cost[top.first][top.second]){
                cost[top.first+dy[i]][top.second+dx[i]] = cost[top.first][top.second];
                q.push_front(make_pair(top.first+dy[i], top.second+dx[i]));//cost 0は push_front
            }
        }

        //ワープ cost 1
        for(long long i = -2; i <= 2; i++){
            for(long long j = -2; j <= 2; j++){
                if(i == 0 and j == 0) continue;

                if(0 <= top.first+i and top.first+i < h and 0 <= top.second+j and top.second+j < w and maze[top.first+i][top.second+j] == '.' and cost[top.first+i][top.second+j] > cost[top.first][top.second]){
                    cost[top.first+i][top.second+j] = cost[top.first][top.second] + 1;
                    q.push_back(make_pair(top.first+i, top.second+j));//cost 1は push_back
                }
            }
        }
    }

    if(cost[gh][gw] == 1e12) cost[gh][gw] = -1;
    printf("%lld\n", cost[gh][gw]);
    return 0;
}

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

int main() {
    int n, k, d;
    cin >> n >> k;
    double dice[n];
    for(int i = 0; i < n; ++i) {
        cin >> d;
        dice[i] = 1 + (d - 1)/2.0;
    }
    double sum = 0.0, ans = 0.0;
    for(int i = 0; i < n; ++i) {
        sum += dice[i];
        if(i >= k-1) {
            ans = max(sum, ans);
            sum -= dice[i-k+1];
        }
        
    }

    printf("%.10lf\n", ans);
    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <string.h>
#include <map>
#include <math.h>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <deque>
#include <stack>
#define ll long long
using namespace std;
string s;
stack <char> q;
int main()
{
    cin>>s;
    int h=s.length();

    for(int i=0;i<h;i++)
    {
        if(q.empty())
        {
            q.push(s[i]);
        }
        else
        {
            if(q.top()!=s[i])
                q.pop();
            else
                q.push(s[i]);
        }
    }
    int h2=q.size();
    cout<<h-h2<<endl;
    return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <numeric>//accumulate(v.begin(), v.end(), 0);
#include <algorithm>//sort(v.begin(),v.end());
#include <string>//
#include <cmath>
#include <iomanip> //setprecision(2)
using namespace std;
#define ll long long
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

int main() {
  int a, b, k;
  cin >> a >> b >> k;
  int res=0;
  for (int i = min(a, b); i >0 ; i--) {
    if (a % i == 0 && b % i == 0) {
      res++;
    }
    if(res==k){
      cout << i << endl;
      return 0;
    }
  }

}


Measured memory_bytes: 256
N,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(N):
    a[i]-=1
if a[0]==0:print(1);exit()
c=dict()
visited=[False]*N
visited[0]=True
c[0]=0
cnt=0
dap=0
n=0
b=[0]
while True:
    n=a[n]
    if visited[n]:
        dap=c[n] 
        break
    visited[n]=True
    b.append(n)
    cnt+=1
    c[n]=cnt
l=len(c)
if k<dap:
    print(b[k]+1)
else:
    print(b[(k-dap)%(l-dap)+dap]+1)

Measured memory_bytes: 40656
#include<bits/stdc++.h>
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repR(i,n) for(ll i=n;i>=0;i--)
#define all(v)(v).begin(),(v).end()
#define rall(v)(v).rbegin(),(v).rend()
#define F first
#define S second
#define pb push_back
#define pu push
#define COUT(x) cout<<(x)<<endl
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,vector<ll>,greater<ll>>
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define mp make_pair
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define sz(x) (int)(x).size()
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MOD = 1000000007LL;
const ll INF = 1LL << 60;
using vll = vector<ll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvll = vector<vll>;
using vstr = vector<string>;
using pll = pair<ll, ll>;
int main(){
  ll n,j;
  cin>>n>>j;
  COUT((n+j-1)/j);
}
  


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

std::vector<int> va;

bool solve(int n, int m)
{
	if (m == 0) return true;

	if (m < 0 || n >= va.size()) return false;

	return solve(n + 1, m - va[n]) || solve(n + 1, m);
}

int main()
{
	int n;
	std::cin >> n;
	while (n--) {
		int a;
		std::cin >> a;
		va.push_back(a);
	}
	n = 0;

	int q;
	std::cin >> q;
	while (q--) {
		int m;
		std::cin >> m;
		if (solve(n, m)) std::cout << "yes";
		else std::cout << "no";
		std::cout << std::endl;
	}

	return 0;
}



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

int main(){
  int L, A, B, C, D;
  
  cin >> L >> A >> B >> C >> D;
  
  int t;
  int a, b;
  a = A / C;
  if(A%C != 0) a++;
  b = B / D;
  if(B%D != 0) b++;
  t = max(a, b);
  cout << L-t << endl;
  return 0;
}

Measured memory_bytes: 1160
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<math.h>
using namespace std;

const int N=1e5+5;
char s[N];int n,a[5];

int main()
{
	scanf("%s",s+1);int i;
	n=strlen(s+1);
	for(i=1;i<=n;++i)
	{
		if(s[i]=='N') a[1]=1;
		if(s[i]=='S') a[2]=1;
		if(s[i]=='W') a[3]=1;
		if(s[i]=='E') a[4]=1;
	}
	
	if(a[1]^a[2]) printf("No\n");
	else if(a[3]^a[4]) printf("No\n");
	else printf("Yes\n");
	
	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);
		int N = sc.nextInt();
		int X = sc.nextInt();
		int m[] = new int[N];
		int sum = 0;

		for (int i = 0; i < N; i++) {
			m[i] = sc.nextInt();
			sum += m[i];
		}

		int min = m[0];

		for (int i = 0; i < m.length; i++) {
			int tmp = m[i];
			if (tmp < min) {
				min = tmp;
			}
		}
		System.out.println(N + (X - sum)/min);
	}
}


Measured memory_bytes: 22740
main = do
    ss <- getLine
    let ns = map (\x -> read x :: Int) $ words $ ss
    
    let ans = if (isIn (ns!!0) (ns!!1) (ns!!2) (ns!!3) (ns!!4))
                then "Yes"
                else "No"
                  where
                    isIn w h x y r = (x-r >= 0) && (y-r >= 0) && (x+r <= w) && (y+r <= h)
    
    putStrLn ans




Measured memory_bytes: 3652
N = int(input())
result = [0] * N
for x in range(1,int((N + 1) ** (1/2))):
  for y in range(1,int((N + 1) ** (1/2))):
    if y > x:
      break
    for z in range(1,int((N + 1) ** (1/2))):
      if z > y:
        break
      a = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
      if a > N:
        break
      if len({x,y,z}) == 1:
        result[a - 1] += 1
      else:
        result[a - 1] += (len({x,y,z}) - 1) * 3
for r in result:
  print(r)

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

int main(){
    int k;
    cin >> k;
    int half;
    if(k%2!=0){
        half = (k-1)/2;
        cout << half * (half+1) << endl;
    }
    else cout << (k/2)*(k/2) << endl;

    return 0;

}

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

#define FOR(i, a, b) for (int i = a; i < (int) b; i++)
#define F0R(i, a) FOR (i, 0, a)
#define GO(to, a) for (auto to : a)

#define f first
#define s second
#define eb emplace_back
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()

int main () {
	int n;
	cin >> n;
	set<int> vis;
	F0R (i, n) {
		int foo;
		cin >> foo;
		if (vis.find(foo) != vis.end()) {
			cout << "NO" << '\n';
			return 0;
		}
		vis.insert(foo);
	}
	cout << "YES" << '\n';
  return 0;
}

Measured memory_bytes: 9600
/**
 *     author: qodjf
 *     created: 04.11.2020 20:40:54
 */
#include <bits/stdc++.h>
using namespace std;

string to_string(string s) { return '"' + s + '"'; }

string to_string(const char* s) { return to_string((string)s); }

string to_string(bool b) { return (b ? "true" : "false"); }

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto& x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifndef ONLINE_JUDGE
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define dbg(...) 42
#endif

#define mst(x, a) memset(x, a, sizeof(x))

using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const ll MOD = 1e9 + 7;

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
ll mul(ll a, ll b) { return a * b % MOD; }

ll add(ll a, ll b) { return (a + b) % MOD; }

ll sub(ll a, ll b) { return (a - b + MOD) % MOD; }

ll my_pow(ll a, ll b) {
    ll r = 1;
    while(b) {
        if(b % 2) {
            r = mul(r, a);
        }
        a = mul(a, a);
        b /= 2;
    }
    return r;
}

ll my_inv(ll a) { return my_pow(a, MOD - 2); }

namespace Comb {
const int MAXK = 2e5 + 5;
int fac[MAXK], inv_fac[MAXK];

void init() {
  fac[0] = inv_fac[0] = 1;
  for (int i = 1; i < MAXK; ++i) {
    fac[i] = mul(fac[i - 1], i);
    inv_fac[i] = my_inv(fac[i]);
  }
}

int C(int a, int b) {
  if (a < 0 || b < 0 || b > a) {
    return 0;
  }
  return mul(fac[a], mul(inv_fac[b], inv_fac[a - b]));
}

}  // namespace Comb

int f(int a, int b) { return Comb::C(a + b, b); }

int main() {
  int H, W, N;
  scanf("%d%d%d", &H, &W, &N);
  vector<P> in(N);
  for (int i = 0; i < N; i++) {
    scanf("%d%d", &in[i].first, &in[i].second);
  }
  in.emplace_back(H, W);
  sort(in.begin(), in.end(), [&](pair<int, int> a, pair<int, int> b) {
    return a.first + a.second < b.first + b.second;
  });

  Comb::init();

  // dp[i] - the number of paths to vertex in[i] such that it's the first
  // forbidden vertex
  vector<int> dp(N + 1);
  for (int i = 0; i <= N; ++i) {
    int tmp = f(in[i].first - 1, in[i].second - 1);
    for (int j = 0; j < i; ++j) {
      if (in[j].first <= in[i].first && in[j].second <= in[i].second) {
        tmp = sub(tmp, mul(dp[j], f(in[i].first - in[j].first,
                                    in[i].second - in[j].second)));
      }
    }
    dp[i] = tmp;
  }

  printf("%d\n", dp[N]);
}


Measured memory_bytes: 1920
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <deque>

int main(){
  long long a, b, c;
  scanf("%lld", &a);
  scanf("%lld", &b);
  scanf("%lld", &c);
  long long left = 4*a*b;
  long long right = (c-a-b)*(c-a-b);
  if (c-a-b<0){
    printf("No\n");
  } else if (left<right){
    printf("Yes\n");
  } else {
    printf("No\n");
  }
  return 0;
}


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

using namespace std;

const long double pi = 3.14159265358979323846;

int main() {
  long double a, b, h, m;
  cin >> a >> b >> h >> m;
  long double rad = pi * 2 * ((h / 12.0) + (m / 60.0) / 12.0 - m / 60.0);
  long double ans =
      (long double)(a * a + b * b) - (long double)(2 * a * b) * cosl(rad);
  printf("%20.20Lf\n", sqrtl(ans));

  return 0;
}

Measured memory_bytes: 4128
//#include "pch.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <map>
#include <iomanip>
#include <math.h> 
#include <stack>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <tuple>
#include <cctype>
#include <ctype.h>
#include <set>
#include <sstream>
#include <time.h>
#include <numeric>
using namespace std;
//#define int long long
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define fi first
#define se second
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))
#define l1 list[index]
#define l2 list[index - 1]
#define l3 list[index + 1]
#define iif(i,j) ((i<0 && j<0) || (i>0 && j>0)) ? true : false 
typedef long long ll;
typedef pair<int, int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
typedef pair<pint, int> P1;
typedef pair<int, pint> P2;
typedef pair<pint, pint> PP;
static const ll maxLL = (ll)1 << 62;
const ll MOD = 1000000007;
const ll INF = 1e18;
const double PI = 3.14159265359;
int ca[12] = { 31,28,31,30,31,30,31,31,30,31,30,31 };



signed main() {
	int n;
	string s, t;

	cin >> n >> s >> t;

	for (int i = 0; i < n; i++) {
		cout << s[i];
		cout << t[i];
	}

	cout << endl;




	return 0;
}

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

int main(){
	int count1=0,count2=0;
	string S;
	cin>>S;
	for(int i=0;i<S.size();i++){
		if(i%2==0){
			if(S[i]=='0'){
				count1++;
			}
		}else{
			if(S[i]=='1'){
				count1++;
			}
		}
	}
	for(int i=0;i<S.size();i++){
		if(i%2==0){
			if(S[i]=='1'){
				count2++;
			}
		}else{
			if(S[i]=='0'){
				count2++;
			}
		}
	}
	cout<<min(count1,count2)<<endl;
	return 0;
}

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

const int MAX_LOG = 30;
int nxt = 10;
int get() { return nxt++; }
int CONSTANT_1;
vector< tuple<char, int, int, int> > operations;

int IS_SMALLER(int i, int j) {
    int k = get();
    operations.push_back(make_tuple('<', i, j, k));
    return k++;
}

int ADD(int i, int j) {
    int k = get();
    operations.push_back(make_tuple('+', i, j, k));
    return k++;
}

int BIN_SHIFT(int i, int by) {
    for(int rep = 0; rep < by; ++rep) {
        i = ADD(i, i);
    }
    return i;
}

int SUB(int i, int j) {
    i = ADD(i, CONSTANT_1);
    int where_diff = get();
    for(int expo = MAX_LOG - 1; expo >= 0; --expo) {
        int power_two = BIN_SHIFT(CONSTANT_1, expo); // can be precomputed
        int should_add = IS_SMALLER(ADD(j, power_two), i);
        should_add = BIN_SHIFT(should_add, expo);
        where_diff = ADD(where_diff, should_add);
        j = ADD(j, should_add);
    }
    return where_diff;
}

int NEGATION(int i) {
    return IS_SMALLER(i, CONSTANT_1);
}

int TERNARY(int i, int j) {
    return SUB(j, BIN_SHIFT(NEGATION(i), MAX_LOG));
}

int MULTIPLY(int i, int j) {
    i = ADD(i, CONSTANT_1);
    int product = get();
    int almost_i = get();
    for(int expo = MAX_LOG-1; expo >= 0; --expo) {
        int power_two = BIN_SHIFT(CONSTANT_1, expo);
        int should_add = IS_SMALLER(ADD(almost_i, power_two), i);
        int j_or_zero = TERNARY(should_add, j);
        should_add = BIN_SHIFT(should_add, expo);
        almost_i = ADD(almost_i, should_add);
        product = ADD(product, BIN_SHIFT(j_or_zero, expo));
    }
    return product;
}

int main() {
    CONSTANT_1 = IS_SMALLER(2, ADD(0, 1));
    int answer = MULTIPLY(0, 1);
    operations.push_back(make_tuple('+', answer, 2, 2));
    cout << operations.size() << "\n";
    for(auto ope : operations) {
    	char c;
    	int x, y, z;
    	tie(c, x, y, z) = ope;
        cout << c << " " << x << " " << y << " " << z << "\n";
    }
}

Measured memory_bytes: 3712
#include<iostream>
using namespace std;
long long n,x,i,a[100000],c[100000],z=0,k;
int main(){
	cin>>n>>x;
	for(i=0;i<n;i++){
		cin>>a[i];
		if(a[i]>x){
			z+=a[i]-x;
			a[i]=x;
		}
	}
	for(i=0;i<n-1;i++){
		if(a[i]+a[i+1]>x){
			k=a[i]+a[i+1]-x;
			z+=k;
			a[i+1]-=k;
		}
	}
	cout<<z;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }
int main(int argc, char* argv[]) {
    unsigned long n,k;
    cin >> n >> k;
    vector<unsigned long> h(n);
    rep(i,n) cin >> h[i];
    sort(ALL(h));
    unsigned long min = pow(10,9);
    rep(i,n-k+1){
        unsigned long t = h[i+k-1]-h[i];
        if(min>t) min = t;
    }
    cout << min << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds; 
#define test() int t;cin>>t;for(int test=1;test<=t;test++)
#define T pair<int, int>
#define ordered_set tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>
#define int long long
#define MOD 1000000007
#define pb push_back 
#define ins insert
#define fast(); ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int m(int a) {
    return ((a%MOD)+MOD)%MOD;
}
int p(int a, int b) {
    if (b==0) return (int)1;
    int x = p(a, b>>1);
    if (b & 1) return m(x*m(a*x));
    return m(x*x);
}
signed main(){
    fast();
    string s;
    cin >> s;
    if(s[2] == s[3] && s[4] == s[5]){
        puts("Yes");
    }
    else puts("No");
}

Measured memory_bytes: 256
#include <stdio.h>
typedef long long ll;
int main() {
	int n, a[200000], list[200000] = {0}, cnt;
	ll ans = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
		if (i - a[i] >= 0)
			list[i - a[i]]++;
	}
	for (int i = 0; i < n; i++) {
		if (a[i] + i <= n - 1)
			ans += list[a[i] + i];
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 3300
#include <stdio.h>

int main()
{
	int a[13] = {0,1,2,1,3,1,3,1,1,3,1,3,1};	
	int x,y;
//	while(){
	scanf("%d%d",&x,&y);
	printf(a[x] - a[y] ? "No" : "Yes");
	return 0;
}

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

const int INF = 1e9+7;
int main(){
  int h,n;cin>>h>>n;
  int dp[h+1];
  int arr[n][2];
  for(int i=0; i<n; i++)cin>>arr[i][0]>>arr[i][1];
  for(int i=0; i<h+1; i++)dp[i] = INF;
  for(int i=1; i<h+1; i++){
    for(int j=0; j<n; j++){
    	if(i-arr[j][0]>0){
          dp[i] = min(arr[j][1]+dp[i-arr[j][0]],dp[i]);
        }else{
          dp[i] = min(dp[i],arr[j][1]);
        }
    }
  }
  cout<<dp[h]<<endl;
  return 0;
}






Measured memory_bytes: 256