akhauriyash/Code-Regression huggingface dataset:
import Foundation

#if swift(>=4.0)
extension String {
    func split(by separator: String) -> [String] {
        return self.components(separatedBy: separator)
    }
    func toArray() -> [String] {
        return self.map{String($0)}
    }
}
func exponentiate(_ lhs: Int, _ rhs: Int) -> Int {
    return (0..<rhs).reduce(1){i,_ in i*lhs}
}
#else
extension String {
    func split(by separator: String) -> [String] {
        return self.componentsSeparatedByString(separator)
    }
    var count: Int {
        return self.characters.count
    }
    func toArray() -> [String] {
        return self.characters.map{String($0)}
    }
    func uppercased() -> String {
        return self.uppercaseString
    }
    func lowercased() -> String {
        return self.lowercaseString
    }
}
//extension Array where Element == String {
//    func joined(separator separator: String) -> String {
//        return self.joinWithSeparator(separator)
//    }
//}
extension Array where Element: Comparable {
    func max() -> Element {
        return self.maxElement()!
    }
    func min() -> Element {
        return self.minElement()!
    }
    func sorted() -> Array {
        return self.sort()
    }
    func reversed() -> Array {
        return self.reverse()
    }
    mutating func sort() {
        self.sortInPlace()
    }
}
extension Array {
    init(repeating: Element, count: Int) {
        self.init(count: count, repeatedValue: repeating)
    }
}
func stride<T: Strideable>(from start: T, to end: T, by stride: T.Stride) -> StrideTo<T> {
    return start.stride(to: end, by: stride)
}
func exponentiate(lhs: Int, _ rhs: Int) -> Int {
    return (0..<rhs).reduce(1){i,_ in i*lhs}
}
#endif
func readInt() -> Int? {
    return Int(readLine()!)
}
func readStringSplit(by separator: String) -> [String] {
    return readLine()!.split(by: separator)
}
func readIntSplit(by separator: String) -> [Int] {
    return readLine()!.split(by: separator).map{Int($0)!}
}

/*************** テストスペース ***************/

//var min, min2, count: Int!
//for i in 1...10 {
//    let x = Int(readLine()!)!
//    if i == 1 {
//        min = x
//        count = 1
//    } else if x < min {
//        min2 = min
//        min = x
//        count = 1
//    } else if x == min && count == 1 {
//        min2 = x
//        count = 2
//    }
//}
//print(min2)

/*************** メインプログラム ***************/

let input = readIntSplit(by: " ")
let (A, B) = (input[0], input[1])
var ans = 0
for i in A...B {
    if String(i).toArray() == String(i).toArray().reversed() {
        ans += 1
    }
}
print(ans)


Measured memory_bytes: 4596
#include <bits/stdc++.h>
#define all(a) (a).begin(), (a).end()
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(i, n) for(int (i)=(n)-1; (i)>=0; (i)--)
#define ios() cin.tie(0), ios::sync_with_stdio(false)
typedef long long ll;
typedef unsigned long long ull;
ll const MOD = 998244353;
ll const INF = 1e18;
using namespace std;

class Combination{
    private:
        ll N;
        ll mod;
        vector<ll> factorial;

    public:
        Combination(ll n, ll m) : N(n), mod(m), factorial(n+1){
            factorial.at(0) = 1;
            for(ll i=1; i<=N; i++){
                factorial.at(i) = i * factorial.at(i-1) % mod;
            }
        }

        ll POW(ll a, ll b){
            ll ans = 1;
            while(b > 0){
                if(b & 1){
                    ans = ans*a % mod;
                }
                a = a*a % mod;
                b >>= 1;
            }
            return ans;
        }

        ll combin(ll n, ll k){
            if(k < 0 || n < k){
                return 1;
            }
            return factorial.at(n) * POW(factorial.at(k)*factorial.at(n-k)%mod, mod-2)%mod;
        }
};

int main(){
    string s;
    cin >> s;

    int n = s.length();
    
    vector<ll> red(n+1, 0);
    REP(i, n){
        int c = 2 - (s[i] - '0');
        red[i+1] = red[i] + c;
    }

    vector<vector<ll>> dp(n+1, vector<ll>(n+1,0));
    dp[0][0] = 1;

    REP(i, n){
        REP(j, n){
            if(red[i+1] >= j+1){
                dp[i+1][j+1] += dp[i][j];
                dp[i+1][j+1] %= MOD;
            }
            if(2*(i+1) - red[i+1] >= i + 1 - j){
                dp[i+1][j] += dp[i][j];
                dp[i+1][j] %= MOD;
            }
        }
    }

    Combination C(n, MOD);
    ll ans = 0;

    REP(i, n+1){
        ans += dp[n][i] * C.combin(n, red[n] - i) % MOD;
        ans %= MOD;
    }

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

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

using namespace std;

using ll = long long;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> p(n);
    for (int i = 0; i < n; i++) cin >> p[i];
    sort(p.begin(), p.end());

    int ans = 0;
    for (int k = 0; k <= 100000; k++) {
        int idx = lower_bound(p.begin(), p.end(), k) - p.begin();
        if (idx * 2 == n) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
  int A, B, C, X;
  cin >> A >> B >> C >> X;
  int count;
  
  for (int i = 0; i <= A; i++) {
    for (int j = 0; j <= B; j++) {
      for (int k = 0; k <= C; k++) {
       int sum = i*500 + j*100 + k*50;
        if (sum == X) {
          count++;
        }
      }
    }
  }
  
  cout << count << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int> >ans;
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++){
            if((n&1)&&i+j==n)continue;
            if(((n&1)^1)&&i+j==n+1)continue;
            ans.push_back(make_pair(i,j));
        }
    printf("%d\n",(int)ans.size());
    for(pair<int,int > p:ans)printf("%d %d\n",p.first,p.second);
    return 0;
}

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

int main() {
    ll N,K;
    cin >> N >> K;
    ll all = N/K;
    if(K %2 ==1){
        cout << all *all  *all << endl;
        return 0;
    }
    ll half = N/(K/2);
    half -= all;
    cout <<all*all*all + half*half*half<< endl;

    return 0;
}

Measured memory_bytes: 3616
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <fstream>
#include <set>
#include <utility>
#include <algorithm>
#include <queue>
#include <stack>
#include <deque>
#include <numeric>
#include <sstream>
#include <list>
#include <map>
#include <functional>
#include <iterator>

#define rep(i,p,n) for(int i=(int)p;i<(int)n;i++)
#define repp(i,p,n) for(int i=(int)p;i>=(int)n;i--)
#define Sort(x) sort(x.begin(),x.end())
#define PSort(x) sort(begin(x), end(x), pairCompare)
#define ll long long
#define INF 2000000000
#define pb push_back
#define mp make_pair
#define PI 3.14159265358979

using namespace std;

int main() {
	int a, b;
	cin >> a >> b;
	cout << (1 + a + b) / 2 << endl;
	

	return 0;
}



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

int main() {
	string s,t;
	cin >> s >> t;
	int ans=0;
	for(int i=0;i<s.size();i++)
	{
		if(s.at(i)!=t.at(i))
		{
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3916
n = int(input())
li = list(map(int,input().split()))

def gcd(a,b):
    while b:
        a,b = b,a%b
    return a

def lcm(c,d):
    return c*d//gcd(c,d)
l = lcm(li[0],li[1])   
for i in range(2,len(li)):
    l = lcm(l,li[i])

ans = 0
for i in range(len(li)):
    ans += (l-1)%li[i]

print(ans)

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

#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
#define MOD 1000000007

int main(){
    int a, b, c, k, mid, min;
    cin >> a >> b >> c;
    cin >> k;
    int sum = 0;
    int m = max({a, b, c});
    if(m==a){
        mid = b;
        min = c;
    }
    else if(m==b){
        mid = a;
        min = c;
    }
    else{
        mid = b;
        min = a;
    }

    for(int i=0; i<k; i++) m = 2*m;
    
    cout << m + min + mid << endl;
    return 0;
}

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

using namespace std;

using ll = long long;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;

int main() {
    ll n, m, i, j, k;
    cin >> n >> k;
    ll r,s,p;
    cin >> r >> s >> p;
    string t;
    cin >> t;
    string x;
    for(i=0;i<t.size();i++){
        if(t[i]=='r'){
            x+='p';
        }else if(t[i]=='p'){
            x+='s';
        }else {
            x+= 'r';
        }
    }
    ll ret = 0;
    bool ch[n]={};
    for(i=0;i<x.size();i++){
        if(ch[i]==1)continue;
        if(i+k<x.size() && x[i]==x[i+k]){
            if(x[i]=='r')ret+=r;
            else if(x[i]=='s')ret+=s;
            else ret+=p;
            ch[i+k]=1;
        }else{
            if(x[i] == 'r')
                ret += r;
            else if(x[i] == 's')
                ret += s;
            else
                ret += p;
        }
    }
    cout << ret << endl;
    //cout << x << endl;
    return 0;
}

Measured memory_bytes: 640
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

int main() {
    int A, B;
    cin >> A >> B;
    int a,b,c,d;
    a = A + A-1;
    b = A + B;
    c = B + B-1;

    int max;
    if (a >= b && a>=c){
        max = a;
    }else if (b >= a && b >= c){
        max =b;
    }else {
        max = c;
    }

    cout << max << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <string>
using namespace std;
int arr[1000000];
int main(){
    int a,b,c,i,n;
    string s[1000];
    cin>>a>>b;
    for(i = 0;i < a;i++){
        cin>>s[i];
    }
    for(i = 0;i < b+2;i++){
        cout<<'#';
    }
    cout<<endl;
    for(i = 0;i< a;i++){
        cout<<'#'<<s[i]<<'#'<<endl;
    }
    for(i = 0;i < b+2;i++){
        cout<<'#';
    }
}


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

using namespace std;

int main() {
    int n, m, x, y;
    cin >> n >> m >> x >> y;

    int xr = x;
    for (int i = 0; i < n; i++) {
        int xi;
        cin >> xi;

        if (xr < xi) {
            xr = xi;
        }
    }

    int yl = y;
    for (int i = 0; i < m; i++) {
        int yi;
        cin >> yi;

        if (yl > yi) {
            yl = yi;
        }
    }

    cout << (xr < yl ? "No War" : "War") << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define INF 1e12

#define PB push_back
#define PF push_front
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vpi vector<pii>
#define vll vector<ll>
#define vpl vector<pll>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define MX(x) *max_element(all(x))
#define MN(x) *min_element(all(x))
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pr_d(x) cout << fixed << setprecision(15) << x << endl
#define ud(c, x) distance(c.begin(), upper_bound(all(c), x))
#define ld(c, x) distance(c.begin(), lower_bound(all(c), x))
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define rep3(i, n) for (int i = (n - 1); i >= 0; --i)
#define rep4(i, a, b) for (int i = (a); i > (b); --i)
#define pb push_back
#define out(x) cout << x << "\n"
bool odd(int i) { return i % 2; }

#define all(v) v.begin(), v.end()
#define size(x) int(x.size())

int gcd(int a, int b) { return __gcd(a, b); }
int lcm(int a, int b) { return a * (b / gcd(a, b)); }
void Yes_No(bool f) {
  if (f)
    printf("Yes\n");
  else
    printf("No\n");
}

void deb_p(pii p) { printf("pair = %d %d\n", p.fi, p.se); }
void deb_i(int i) { printf("i = %d\n", i); }
void deb_v(vector<int> v) {
  printf("v = ");
  for (auto i : v) printf("%d ", i);
  printf("\n");
}
template <typename T>
bool chmax(T& a, const T& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T& a, const T& b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
//-------------------ここから回答する-----------------------

void solve(void) {
  ll a, b, c, d;
  cin >> a >> b >> c >> d;
  if (a * b >= c * d)
    out(a * b);
  else
    out(c * d);
}
int main(void) { solve(); }

Measured memory_bytes: 3632
#include <stdio.h>

#define MAX 44

int A[MAX];

int fibonacci(int n)
{
  int i;
  A[0]=1;
  A[1]=1;
  for(i=2;i<=n;i++){
    A[i]=A[i-2]+A[i-1];
  }

}
    

int main(){
  int a;

 
  scanf("%d",&a);
   fibonacci(a);
  printf("%d\n",A[a]);
  return 0;
}


Measured memory_bytes: 2104
lines = []
while line = gets
    lines << line.chomp.split(' ').map(&:to_i)
end

N = lines[0][0]

ans = 0
max = 0
for i in 1..N do
  if lines[1][i-1] >= max then
    ans += 1
    max = lines[1][i-1]
  end
end
  
puts ans

Measured memory_bytes: 14296
count =[[[0]*10 for j in range(3)] for k in range(4)]
n = int(input())
for x in range(n):
    b,f,r,v = map(int,input().split())
    # 1 <= b <=4
    # 1 <= f <= 3
    # 1 <= r <= 10
    # 1 <= v <= 9
    count[b-1][f-1][r-1] += v
    
for i in range(4):
    if i != 0:
        print("#"*20)
    for j in range(3):
        for k in range(10):
            print(f' {count[i][j][k]}',end="")
        print()


Measured memory_bytes: 5636
#!/usr/bin/python3
# import bisect
# from collections import Counter, deque, OrderedDict, defaultdict
# from copy import copy, deepcopy # pythonのみ．copyは1次元，deepcopyは多次元．
# from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    n,m=map(int,input().split())
    A=[list(map(int,input().split())) for i in range(n)]
    val=0
    for i in A:
        val+=sum(i)
    # bit全探索    
    # https://qiita.com/gogotealove/items/11f9e83218926211083a#%E4%BE%8B%E9%A1%8C-1
    # 昇順での探索だよ
    ans=0
    for i in range(2 ** 3):
        val=[sum(i) for i in A]

        
        """        
        10進数表記　2進数表記
        0           000
        1           001
        2           010
        3           011
        4           100
        5           101
        6           110
        7           111
        """
    
        for j in range(3):  # このループが一番のポイント
            if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
                for k in range(n):
                    val[k]-=2*A[k][j]
        val.sort(reverse=True)
        ans=max(ans,sum(val[:m]))
    print(ans)

    

    
resolve()

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

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(), (x).end()

typedef int64_t ll;
typedef long double ld;

const int INF = 1e9;
const ld EPS = 1e-8;

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main(){
  int N;
  cin >> N;
  vector<ld> A(N);
  REP(i, N) cin >> A[i];

  ld ret = 0;
  REP(i,N) ret += 1 / A[i];
  ret = 1 / ret;

  cout << fixed << setprecision(10) << ret << endl;
  return 0;
}



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

int dp[3000][3000];
// dp[x][y] = s wali string mein x index par hain, t wali string mein y index par... max length

int choice[3000][3000];
// 0 -> (i-1,j) , 1 -> (i,j-1) , 2 -> pick and goto (i-1,j-1)

int main(){
	string s,t;
	cin>>s>>t;
	
	int n = s.size(), m = t.size();
	
	dp[0][0] = 0;
	
	if(s[0] == t[0]){
		dp[0][0] = 1;
		choice[0][0] = 2;
	}
	
	for(int i = 0 ; i < n; i++){
		for(int  j = 0 ; j < m ; j++){
			// not picking current character
			if(i > 0){
				dp[i][j] = dp[i-1][j];
				choice[i][j] = 0;
			}
			if(j > 0){
				if(dp[i][j-1] > dp[i][j]){
					dp[i][j] = dp[i][j-1];
					choice[i][j] = 1;
				}
			}
			// pick current character
			if(s[i] == t[j]){
				int ans = 1;
				if(i>0 && j>0){
					ans = 1 + dp[i-1][j-1];
				}
				if(ans > dp[i][j]){
					dp[i][j] = ans;
					choice[i][j] = 2;
				}
			}
		}
	}
	
	int i = n-1, j = m-1;
	
	string subsequence;
	
	while(i >= 0 && j >= 0){
		if(choice[i][j] == 0){
			i--;
		}
		else if(choice[i][j] == 1){
			j--;
		}
		else{
			subsequence.push_back(s[i]); // or t[j]
			i--;
			j--;
		}
	}
	
	reverse(subsequence.begin(), subsequence.end());
	cout<<subsequence;
	
}

Measured memory_bytes: 73936
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s;
	cin>>s;
	int x=0,t=0;
	for(int i=0;i<3;i++)
	{
		if(s[i]=='R'){x++;t=max(t,x);}
		else x=0;
	}
	cout<<t;
	return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <cstdio>
#include <string>
#include <unordered_set>

#define set unordered_set
#define ll long long

using namespace std;

const ll maxn = 4000;
const ll base = maxn+1;
const ll maxx = 255;
const ll oo = 1000000007;
const ll oo2 = 1000000009;
const ll oo3 = 1000000023;
const ll oo4 = 1000000003;

ll n,m;
string s1,s2;
ll pw[maxn+1],pw2[maxn+1],pw3[maxn+1],pw4[maxn+1]; // pow(maxx,x)
ll has1[maxn+1],has2[maxn+1],has12[maxn+1],has22[maxn+1],has13[maxn+1],has23[maxn+1],has14[maxn+1],has24[maxn+1];

set<ll> S,S2,S3,S4;

ll init()
{
	pw[0]=1;
	for (ll i=1; i<=maxn; i++)
		pw[i]=(pw[i-1]*base)%oo;
	pw2[0]=1;
	for (ll i=1; i<=maxn; i++)
		pw2[i]=(pw2[i-1]*base)%oo2;
	pw3[0]=1;
	for (ll i=1; i<=maxn; i++)
		pw3[i]=(pw3[i-1]*base)%oo3;
	pw4[0]=1;
	for (ll i=1; i<=maxn; i++)
		pw4[i]=(pw4[i-1]*base)%oo4;
}

int main()
{
	ios_base::sync_with_stdio(0);
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	init();
	cin >> s1 >> s2;

	if (s1.size()>s2.size())
	{
		string t;
		t=s1;
		s1=s2;
		s2=t;
	}

	n=s1.size();
	m=s2.size();
	s1=' '+s1;
	s2=' '+s2;
	
	has1[0]=0;
	for (ll i=1; i<=n; i++)
		has1[i]=(has1[i-1]+pw[(ll) s1[i]])%oo;
	has2[0]=0;
	for (ll i=1; i<=m; i++)
		has2[i]=(has2[i-1]+pw[(ll) s2[i]])%oo;
	has12[0]=0;
	for (ll i=1; i<=n; i++)
		has12[i]=(has12[i-1]+pw2[(ll) s1[i]])%oo2;
	has22[0]=0;
	for (ll i=1; i<=m; i++)
		has22[i]=(has22[i-1]+pw2[(ll) s2[i]])%oo2;
	has13[0]=0;
	for (ll i=1; i<=n; i++)
		has13[i]=(has13[i-1]+pw3[(ll) s1[i]])%oo3;
	has23[0]=0;
	for (ll i=1; i<=m; i++)
		has23[i]=(has23[i-1]+pw3[(ll) s2[i]])%oo3;
	has14[0]=0;
	for (ll i=1; i<=n; i++)
		has14[i]=(has14[i-1]+pw4[(ll) s1[i]])%oo4;
	has24[0]=0;
	for (ll i=1; i<=m; i++)
		has24[i]=(has24[i-1]+pw4[(ll) s2[i]])%oo4;


	for (ll i=n; i>=1; i--)
	{
		S.clear();
		S2.clear();
		S3.clear();
		S4.clear();
		for (ll x=1; x+i-1<=n; x++)
		{
			//cout << x << ' ' << x+i-1 << ' ' << (has1[x+i-1]-has1[x-1]+oo)%oo << '\n';
			S.insert((has1[x+i-1]-has1[x-1]+oo*oo)%oo);
			S2.insert((has12[x+i-1]-has12[x-1]+oo2*oo2)%oo2);
			S3.insert((has13[x+i-1]-has13[x-1]+oo3*oo3)%oo3);
			S4.insert((has14[x+i-1]-has14[x-1]+oo4*oo4)%oo4);
		}
		//cout << '\n';
		for (ll x=1; x+i-1<=m; x++)
		{
			//cout << x << ' ' << x+i-1 << ' ' << (has2[x+i-1]-has2[x-1]+oo)%oo << '\n';
			if 	(S.count((has2[x+i-1]-has2[x-1]+oo*oo)%oo)
				and S2.count((has22[x+i-1]-has22[x-1]+oo2*oo2)%oo2)
				and S3.count((has23[x+i-1]-has23[x-1]+oo3*oo3)%oo3)
				and S4.count((has24[x+i-1]-has24[x-1]+oo4*oo4)%oo4))
			{
				cout << i << '\n';
				return 0;
			}
		}
		//cout << "\n\n";
	}
	cout << 0 << '\n';
	return 0;
}

Measured memory_bytes: 4164
#include <iostream>
#include <algorithm>
#include <tuple>
#include <vector>
#include <string>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <cassert>

using namespace std;
using ll = long long;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n), ans(n);
    ll tot = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        tot += a[i];
    }
    ans[0] = tot;
    for(int i = 1; i < n; i += 2) {
        ans[0] -= (2 * a[i]);
    }

    for(int i = 0; i < n; i++){
        if(i+1 == n){
            ans[0] = 2 * a[i] - ans[i];
        }else{
            ans[i+1] = 2 * a[i] - ans[i];
        }
    }
    for(int i = 0; i < n; i++){
        cout << ans[i] << " ";
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 4032
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <cassert>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define srep(i,n,m) for(int i=n;i<m;i++)
#define elif else if
#define INF 1000000007
#define pi 3.141592653589793
using namespace std;
int saidaikouyakusuu(int a,int b){
    if(b==0) return a;
    return saidaikouyakusuu(b,a%b);
}
int saisyoukoubaisuu(int a,int b){
    return a*b/saidaikouyakusuu(a,b);
}
int n,m,cnt=0,aa[220000],d,ab[500][50],ac[500],ad[50];
pair<int,int> pp[220000];
string s,ss[220000];
char c;
queue<int> que;
signed main(){
    cin>>d;
    rep(i,26){
        cin>>aa[i];
    }
    rep(i,d){
        rep(j,26){
            cin>>ab[i][j];
        }
    }
    rep(i,d){
        ac[i]=0;
        m=-INF;
        rep(j,26){
            cnt=0;
            cnt+=ab[i][j+1];
            rep(k,26){
                if(k!=j){
                    cnt-=(ad[k]+1)*aa[k];
                }
            }
            if(m<cnt){
                ac[i]=j+1;
                m=cnt;
            }
        }
        rep(j,26){
            if(j+1==ac[i]){
                ad[j]=0;
            }else{
                ad[j]++;
            }
        }
        cout<<ac[i]<<endl;
    }
}

Measured memory_bytes: 10652
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define ff first
#define VI vector <int>
#define ss second
#define pii pair<int, int>
#define pci pair<char, int>
#define mii map<int, int>
#define mci map<char, int>
#define setbits(n) __builtin_popcount(n)
#define fill(a,b) memset(a, b, sizeof(a))
#define all(v) (v).begin(), (v).end()
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define PI 3.14159265
const long long N=1e9;

int lcm(ll a, ll b){
    ll g=__gcd(a, b);
    return a/g*b;
}
void dfs(int u, vector<vector<int>>& g, bool vis[]){
    vis[u]=true;
    for (int i: g[u]){
        if (!vis[i]){
            dfs(i, g, vis);
        }
    }
}
int main(){
    IOS;
	int t;
	t=1;
// 	cin>>t;
	while (t--){
	    int n, m;
	    cin>>n>>m;
	    vector<vector<int>> g(n+1, vector<int>());
	    bool vis[n+1]={};
	    for (int i=0; i<m; i++){
	        int x, y;
	        cin>>x>>y;
	        g[x].pb(y);
	        g[y].pb(x);
	    }
	    int cnt=0;
	    for (int i=1; i<=n; i++){
	        if (!vis[i]){
	            cnt++;
	            dfs(i, g, vis);
	        }
	    }
	    cout<<cnt-1;
	}
	return 0;
}


Measured memory_bytes: 9784
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

S = input()
T = input()
if len(S) < len(T):
    print('UNRESTORABLE')
    exit()
result = []
for sidx, s in enumerate(S):
    #  print('sidx,s', sidx, s)
    # どこから始めるかで考える
    if sidx + len(T) > len(S):
        continue
    for tidx, t in enumerate(T):
        #  print('tidx, t', tidx, t)
        if S[sidx+tidx] == '?':
            continue
        if t != S[sidx+tidx]:
            # 一致しない場合はこれではない
            break
    else:
        # 鍵発見
        #  print('sidx', sidx)
        ans = S[:sidx] + T
        if sidx + len(T) < len(S):
            ans += S[sidx+len(T):]
        ans = ans.replace('?', 'a')
        result.append(ans)
if result:
    print(min(result))
else:
    print('UNRESTORABLE')


Measured memory_bytes: 65004
#include <cstdio>
#include <algorithm>

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

using namespace std;

const int inf = 1e6;

int n, m, s, x, y;
int g[100][100];

int main(){
	while(scanf("%d", &n), n){
		rep(i, n){
			rep(j, n){
				g[i][j] = inf;
			}
			g[i][i] = 0;
		}
		scanf("%d%d%d%d", &m, &s, &x, &y);
		rep(i, m){
			int a, b, c;
			scanf("%d%d%d", &a, &b, &c);
			g[a - 1][b - 1] = c;
		}
		rep(k, n){
			rep(i, n){
				rep(j, n){
					g[i][j] = min(g[i][k] + g[k][j], g[i][j]);
				}
			}
		}
		int ans = inf;
		rep(i, n){
			ans = min(g[s - 1][i] + g[i][x - 1] + g[i][y - 1], ans);
		}
		printf("%d\n", ans);
	}
	return 0;
}

Measured memory_bytes: 1064
#include <iostream>
//#include <queue>
//#include <vector>
#include <map>
//#include <algorithm>
#define int long long
using namespace std;
int N,M,A[1000007];
//vector<int> l;
map<int,int> m;
//priority_queue<int> q;
signed main(void){
    cin >> N >> M;
    int allsum=0,count=0;
    for(int i=0; i<N; i++){
        cin >> A[i];
        allsum += A[i];
        int k = A[i];
        while(k>0){
            m[k-k/2]= ((m.find(k-k/2)==m.end())? 0: m[k-k/2]) + 1;
            //l.push_back(k-k/2);
            //q.push(k-k/2);
            //count++;
            k = k/2;
        }
    }
    //sort(l.begin(), l.end(), greater<int>());
    int sum=0, c=0;
    //for(int i=0; i<M&&i<count; i++){
    //    sum += l[i];
    for(auto itr=m.rbegin(); itr!=m.rend(); itr++){
        int key=itr->first, val=itr->second;
        if(c+val<=M){
            sum += key*val;
            c += val;
        }else{
            sum += key*(M-c);
            break;
        }
    //for(int i=0; i<M && i<count; i++){
    //    sum += q.top(); q.pop();
    }
    cout << allsum-sum << "\n";
}

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

int main() {
    string s; cin >> s;

    int cnt = 0;
    int max_cnt = 0;
    for(int i=0; i<s.size(); i++){
        if(s.at(i)=='A' || s.at(i)=='C' || s.at(i)=='G' || s.at(i)=='T'){
            cnt++;
            max_cnt = max(cnt, max_cnt);
        }
        else
        {
            max_cnt = max(cnt, max_cnt);
            cnt = 0;
        }
    }

    cout << max_cnt << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
int main() {
  ll k, q;
  cin >> k >> q;
  ll d[k];
  rep(i,k)
  {
    cin >> d[i];
  }
  rep(i,q)
  {
    int n, x, m;
    cin >> n >> x >> m;
    ll d1 = 0, eq1 = 0,dm;
    n = n - 1;
    int nkm = n % k;
    int nkd = (n / k);
    rep(j,k)
    {
      dm=d[j] % m;
      if (dm) {
        d1 += dm * nkd;
        if (j < nkm) {
          d1 += dm;
        }
      } else {
        eq1 += nkd;
        if (j < nkm) {
          eq1++;
        }
      }
    }
    d1 += x;
    cout << n - (d1 / m - x / m) - eq1 << endl;
  }
}

Measured memory_bytes: 384
#include <stdio.h>
#include <string.h>

int main(void){
	double t, tt;
	
	while(scanf("%lf %lf", &t, &tt) != EOF){
		char rank[5] = "NA";
		if(t<35.5 && tt<71) strcpy(rank,"AAA");
		else if(t<37.5 && tt<77) strcpy(rank,"AA");
		else if(t<40 && tt<83) strcpy(rank,"A");
		else if(t<43 && tt<89) strcpy(rank,"B");
		else if(t<50 && tt<105) strcpy(rank,"C");
		else if(t<55 && tt<116) strcpy(rank,"D");
		else if(t<70 && tt<148) strcpy(rank,"E");
		
		printf("%s\n", rank);	
	}	

	return 0;
}

Measured memory_bytes: 608
// execute g++ main.cpp -std=c++14 -I C:\Users\naoya\Desktop\code\Atcoder
#include<bits/stdc++.h>
//#include<atcoder/all>
typedef long long ll;
typedef long double ld;
using namespace std;
//using namespace atcoder;

using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

#define REP(i, l, n) for(int i=(l), i##_len=(n); i<i##_len; ++i)
#define ALL(x) (x).begin(),(x).end()
#define pb push_back

ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

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


char alpha[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};

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

int N, Q;
struct LazySegmentTree {
private:
    int n;
    vector<ll> node, lazy;

public:
    LazySegmentTree(vector<ll> v) {
        int sz = (int)v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1);
        lazy.resize(2*n-1, 0);

        for(int i=0; i<sz; i++) node[i+n-1] = v[i];
        for(int i=n-2; i>=0; i--) node[i] = node[i*2+1] + node[i*2+2];
    }

    void eval(int k, int l, int r) {
        if(lazy[k] != 0) {
            node[k] += lazy[k];
            if(r - l > 1) {
                lazy[2*k+1] += lazy[k] / 2;
                lazy[2*k+2] += lazy[k] / 2;
            }
            lazy[k] = 0;
        }
    }

    void add(int a, int b, ll x, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b) {
            lazy[k] += (r - l) * x;
            eval(k, l, r);
        }
        else {
            add(a, b, x, 2*k+1, l, (l+r)/2);
            add(a, b, x, 2*k+2, (l+r)/2, r);
            node[k] = node[2*k+1] + node[2*k+2];
        }
    }

    ll getsum(int a, int b, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return 0;
        if(a <= l && r <= b) return node[k];
        ll vl = getsum(a, b, 2*k+1, l, (l+r)/2);
        ll vr = getsum(a, b, 2*k+2, (l+r)/2, r);
        return vl + vr;
    }
};

const ll mod = 998244353;
int main() {
    cin >> N >> Q;
    LazySegmentTree seg( vector<ll>(N, 0) );
    vector<vector<int> > lis(N, vector<int>(2));
    REP(i, 0, Q){
        cin >> lis[i][0] >> lis[i][1];
    }
    seg.add(0, 1, 1);
    REP(i, 0, N){
        ll k = seg.getsum(i, i+1);
        k %= mod;
        REP(l, 0, Q){
            int s = i + lis[l][0], t = min(i + lis[l][1] + 1, N);
            seg.add(s, t, k);
        }
    }
    cout << seg.getsum(N-1, N) % mod << endl;
    /*for(int i=0; i<Q; i++) {
        int query; cin >> query;
        if(query == 0) {
            int s, t, x; cin >> s >> t >> x;
            seg.add(s-1, t, x);
        }
        else {
            int s, t; cin >> s >> t;
            cout << seg.getsum(s-1, t) << endl;
        }
    }*/
    return 0;
}

Measured memory_bytes: 22432
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma warning(disable : 4996)
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<time.h>
#include<random>
#include<array>


using namespace std;

#define REP(i, n) for(int i = 0;i < n;++i)
#define REPR(i, n) for(int i = n-1;i >= 0;--i)
#define FOR(i, m, n) for(int i = m;i < n;++i)
#define FORR(i, m, n) for(int i = m-1;i >= n;--i)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define print(x) cout<<(x)<<'\n'
#define pe(x) cout<<(x)<<" "
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define lb(v,n) lower_bound(v.begin(), v.end(), (n))
#define ub(v,n) upper_bound(v.begin(), v.end(), (n))
//#define int long long
//#define double long double
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i,v.size())cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")
template<typename T1, typename T2> inline void chmin(T1 & a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
typedef pair<int, int>P;
std::random_device rd;
std::mt19937 mt(rd());
constexpr int MOD = 1e9 + 7; constexpr int MAX = 200020;
const double pi = acos(-1); constexpr double EPS = 1e-8;
constexpr ll INF = 1e16;
typedef array<int, 3>arr3;


bitset<4005000>dp;
void solve() {
	int N; cin >> N;
	int sum = 0;
	vector<int>A(N);
	REP(i, N) {
		cin >> A[i];
		sum += A[i];
	}
	int mid = (sum + 1) / 2;

	dp[0] = true;

	REP(i, N) {
		dp |= (dp << A[i]);
	}

	FOR(i, mid, sum + 1) {
		if (dp[i]) {
			print(i); return;
		}
	}
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//int q; cin >> q;
	//while (q--)
		solve();
}



Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define N 3005
#define T 3005
#define int long long
using namespace std;
typedef pair<int,int> P;

int dp[N][T], A[N], B[N];
P AB[N];

signed main(){
  
  int n, t;
  cin>>n>>t;
  
  for(int i=0;i<n;i++){
    cin>>A[i]>>B[i];
    AB[i] = P(A[i],B[i]);
  }
  
  sort(AB,AB+n);
  
  for(int i=0;i<n;i++){
    
    for(int j=0;j<=t;j++){
      
      dp[i+1][j] = max( dp[i+1][j], dp[i][j] );
      
      if( j == t ) continue;
      
      int nj = j + AB[i].first;
      
      if( nj > t ) nj = t;
      
      dp[i+1][nj] = max( dp[i+1][nj], dp[i][j] + AB[i].second );
      
    }
    
  }
  
  int ans = 0;
  
  for(int i=0;i<=t;i++){
    ans = max( ans, dp[n][i] );
  }
    
  cout<<ans<<endl;
  
  return 0;
}


Measured memory_bytes: 70784
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vvin=vector<vector<int>>;
using vvll=vector<vector<long long>>;
using vstr=vector<string>;
using vvstr=vector<vector<string>>;
using vch=vector<char>;
using vvch=vector<vector<char>>;
using vbo=vector<bool>;
using vvbo=vector<vector<bool>>;
using vpii=vector<pair<int,int>>;
using pqsin=priority_queue<int,vector<int>,greater<int>>;
#define mp make_pair
#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++)
#define all(v) v.begin(),v.end()
#define decp(n) cout<<fixed<<setprecision((int)n)
const int inf=1e9+7;
const ll INF=1e18;

int main(){
    int n,m,x;cin>>n>>m>>x;
    vin c(n);
    vvin a(n,vin(m));
    rep(i,n){
        cin>>c[i];
        rep(j,m)cin>>a[i][j];
    }
    vin understand(m);
    int sum;
    bool can;
    int mi=inf;
    rep(i,1<<n){
        bitset<15> tmp(i);
        rep(i,m)understand[i]=0;
        sum=0;
        rep(j,n){
            can=true;
            if(tmp[j]){
                sum+=c[j];
                rep(k,m){
                    understand[k]+=a[j][k];
                    if(can&&understand[k]<x)can=false;
                }
            }
            if(can&&tmp[j]){
                mi=min(mi,sum);
                break;
            }
        }
    }
    if(mi!=inf)cout<<mi<<endl;
    else cout<<-1<<endl;
}

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

using namespace std;

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

	int n,k;
	cin >> n >> k;
	int p[n];
	for(int i=0; i<n; i++){
		cin >> p[i];
	}
	sort(p,p+n);
	int sum=0;
	for(int i=0; i<k; i++){
		sum += p[i];
	}
	cout << sum;
	return 0;
}

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



int main() {
#ifdef HOME
    assert(freopen("in", "r", stdin));
#endif


    int n;
    while (scanf("%d", &n) == 1) {
        vector<int> a(n);
        ll sum = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            sum += a[i];
        }

        ll ans = 1e18;
        ll s1 = 0;
        for (int i = 0; i < n - 1; i++) {
            s1 += a[i];
            ans = min(ans, abs(s1 - (sum - s1)));
        }
        cout << ans << endl;
    }


#ifdef HOME
    cerr << "time: " << clock() * 1.0 / CLOCKS_PER_SEC << endl;
#endif
    return 0;
}

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

K = -1
for k in range(N+1):
    if k*(k-1)//2 == N:
        K = k
        break
    elif k*(k-1)//2 > N:
        break

if N == 1:
    print('Yes')
    print(2)
    print(1, 1)
    print(1, 1)
elif K == -1:
    print('No')
else:
    print('Yes')
    print(K)
    n = 0
    S = [[] for _ in range(K)]
    for i in range(K):
        for j in range(i+1, K):
            n += 1
            S[i].append(n)
            S[j].append(n)
    for s in S:
        print(len(s), ' '.join([str(a) for a in s]))

Measured memory_bytes: 9076
#define _USE_MATH_DEFINES
# include <bits/stdc++.h>
using namespace std;
int main() {
    long long N,C;
    cin >> N>>C;
    long long x[100000],v[100000];
    long long f[100000],g[100000];
    long long when[100000];
    long long i_made[100000];
    
    long long v_sum=0;
    long long res=0;
    for (int i = 0; i < N; i++) {
        cin >> x[i] >> v[i];
        v_sum+=v[i];
        i_made[i]=v_sum;
        f[i]=i_made[i]-x[i];
        if(i>0){
            g[i]=max(g[i-1],f[i]);
        }else{
            g[0]=max(f[i],(long long)0);
        }
        if(g[i]!=f[i]){
            if(i>0){
                when[i]=when[i-1];
            }else{
                when[i]=100001;
            }
        }else{
            when[i]=i;
        }
    }
    
    for (int i = 1; i < N; i++) {
        long long cost;
        long long score;
        cost=(C-x[i])*2;
        score=v_sum-i_made[i-1]+g[i-1];
        res=max(res,score-cost);
    }
    res=max(res,v_sum-(C-x[0]));
    res=max(res,g[N-1]);
    v_sum=0;
    for (int i = 0; i < N; i++) {
        long long r_i=N-1-i;
        v_sum+=v[r_i];
        i_made[i]=v_sum;
        f[i]=i_made[i]-(C-x[r_i]);
        if(i>0){
            g[i]=max(g[i-1],f[i]);
        }else{
            g[0]=max(f[i],(long long)0);
        }
        if(g[i]!=f[i]){
            if(i>0){
                when[i]=when[i-1];
            }else{
                when[i]=100001;
            }
        }else{
            when[i]=i;
        }
    }
    
    for (int i = 1; i < N; i++) {
        long long r_i=N-1-i;
        long long cost;
        long long score;
        cost=x[r_i]*2;
        score=v_sum-i_made[i-1]+g[i-1];
        res=max(res,score-cost);
    }
    res=max(res,v_sum-x[N-1]);
    res=max(res,g[N-1]);
    cout << res<<endl;
    return 0;
}

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

using namespace std;

long long v[500][500];
long long g[500][500];

int n, m, l;

int main()
{
    cin >> n >> m >> l;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) v[i][j] = 1e12;
    for (int i = 1; i <= n; i++) v[i][i] = 0;
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        v[a][b] = c;
        v[b][a] = c;
    }
    for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) v[i][j] = min(v[i][k] + v[k][j], v[i][j]);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) g[i][j] = 1e12;
    for (int i = 1; i <= n; i++) g[i][i] = 0;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (i != j && v[i][j] <= l) g[i][j] = 1;
    for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) g[i][j] = min(g[i][k] + g[k][j], g[i][j]);
    int q;
    cin >> q;
    while (q--)
    {
        int a, b;
        cin >> a >> b;
        if (g[a][b] > 1e9) cout << -1 << "\n";
        else cout << g[a][b] - 1 << "\n";
    }
}


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

int main(){
  long long N;
  cin >> N;
  map<long long, long long> mp;
  vector<long long> A(N);
  for (int i=0; i<N; i++){
    cin >> A[i];
    mp[A[i]]++;
  }
  sort(A.begin(), A.end(), greater<long long>());
  vector<long long> check;
  long long hoge = 2;
  for (int i=0; i<31; i++){
    check.push_back(hoge);
    hoge *= 2;
  }
  sort(check.begin(), check.end(), greater<long long>());
  long long ans = 0;
  for (long long i: A){
    if (mp[i]==0) continue;
    for (long long j: check){
      if (j <= i) break;
      long long ni = j-i;
      if (ni!=i){
        if (mp[ni]>0)
        {
          ans++;
          mp[i]--;
          mp[ni]--;
          break;
        }
      }
      else
      {
        if (mp[i]>1){
          ans++;
          mp[i]-=2;
          break;
        }
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 52736
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define INF 2e9
#define LINF 1e18
#define MOD 1000000007
#define rep(i, n) for(int i = 0; i < (ll)(n); i++)
#define input(x, n)for(int i = 0; i <(ll)(n); i++)cin >> x[i];
#define until(i,n) for(int i = 1; i <= (ll)(n); i++)
#define all(x) (x).begin(),(x).end()
#define dump(x) cout << #x << "=" << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO")
#define Yes(n) cout << ((n) ? "Yes" : "No")
#define PI 3.141592653589793

int main(){
    
    int n;
    cin >> n;
    vector<ll> a(n);
    vector<ll> B(n+1, 0);
    ll sum = 0;
    rep(i, n){
        cin >> a[i];
        B[i+1] = B[i]+a[i];
    }

    ll ans = 0;

    rep(i, n){
        ll sum = (B[n] - B[i+1])%MOD;
        ans += a[i]*sum;
        ans %= MOD;
    }

    cout << ans << endl;

}

Measured memory_bytes: 6384
#!/usr/bin/env ruby

require 'set'

class Hash
  def push(key, value)
    self[key] = [] if self[key] == nil
    self[key].push(value)
  end
end

class Array
  def lower_bound(value)
    left = -1;
    right = self.length;
    while left + 1 < right
      mid = left + (right - left) / 2;
      if self[mid] >= value
        right = mid
      else
        left = mid
      end
    end
    right
  end

  def unique
    res = [self.first]
    each_cons(2) do |a, b|
      if a != b
        res.push(b)
      end
    end
    res
  end
end

def get_ints
  gets.chomp.split.map(&:to_i)
end

def get_ints_minus_one
  get_ints.map { |x| x - 1 }
end

def get_int
  gets.chomp.to_i
end

A, B = get_ints

a = A - 1
count = 1
ans = 0
while count < B
  count += a
  ans += 1
end

puts ans


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

using namespace std;


int main(){
    string str;
    int A,B;

    cin>>A>>B>>str;

    for(int i=0;i<str.size();++i){
        if(i==A){
            if(str[i]!='-'){
                cout<<"No"<<endl;
                return 0;
            }
        }else{
            if(str[i]=='-'){
                cout<<"No"<<endl;
                return 0;
            }
        }
    }

    cout<<"Yes"<<endl;
}


Measured memory_bytes: 256
from collections import deque
n = int(input())
a = list(map(int, input().split()))

stack = deque()
for i in range(n):
    if i % 2 == 0: stack.append(a[i])
    else: stack.appendleft(a[i])
ans = list(stack)
if n % 2 != 0: ans = ans[::-1]
print(" ".join(map(str, ans)))

Measured memory_bytes: 30660
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
*/

int main(){
    string s; cin >> s;

    stack<int> st1;
    stack<pair<int,int>> st2;

    int sum = 0;
    for(int i=0; i<s.size(); i++){
        if(s[i] == '\\'){
            st1.push(i);
        }
        else if(s[i] == '/' && st1.size()>0){
            int j = st1.top(); st1.pop();
            sum += i-j;
            int a = i-j;
            while(st2.size()>0 && st2.top().first > j){
                a += st2.top().second; st2.pop();
            }
            st2.push({j, a});
        }
    }

    // 出力
    vector<int> ans;
    while(st2.size() > 0){
        ans.push_back(st2.top().second);
        st2.pop();
    }
    reverse(ans.begin(), ans.end());

    cout << sum << endl;
    cout << ans.size();
    for(int i=0; i<ans.size(); i++) cout << " " << ans[i];

    cout << endl;
    return 0;
}


Measured memory_bytes: 3256
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
#include<list>
#include<set>
#include<cstring>
using namespace std;

int main() {
  string s; cin >> s;
  int c = 0;
  for(int i=0; i<s.size(); i++) {
    if(s[i] == '2') c++;
  }
  cout << c << endl;

  return 0;
}

//


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**9)
def input():
    return sys.stdin.readline().rstrip()

def main():
    S=list(input())
    pre=0
    ans=0
    m=0
    p=0
    for a in S:
        if a =='<':
            p+=1
            if m != 0:
                ans-=min(pre,m)
                pre=m
                ans+=m*(m+1)//2
                m=0
        elif a=='>':
            m+=1
            if p!=0:
                pre=p
                ans+=p*(p+1)//2
                p=0
    if m != 0:
        ans-=min(pre,m)
        pre=m
        ans+=m*(m+1)//2
        m==0
    elif p!=0:
        pre=p
        ans+=p*(p+1)//2
        p==0
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 89820
#include<map>
#include<bitset>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<stack>

#define REP(i,x,y) for(ll i=x;i<=y;i++)
typedef long long ll;
using namespace std;
ll const MAX = 505;
ll grid[MAX][MAX];
ll const MAX2 = MAX * MAX;
ll ans[MAX2][5];
ll cnt = 0;

int main() {
	ll h, w;
	cin >> h >> w;
	REP(i, 1, h) {
		REP(j, 1, w) {
			cin >> grid[i][j];
		}
	}
	REP(i, 1, h) {
		if (i % 2 == 1) {
			REP(j, 1, w-1) {
				if (grid[i][j] % 2 == 1) {
					cnt++;
					ans[cnt][1] = i;
					ans[cnt][2] = j;
					ans[cnt][3] = i;
					ans[cnt][4] = j + 1;
					grid[i][j + 1] ++;
				}
			}
			if (i < h) {
				if (grid[i][w] % 2 == 1) {
					cnt++;
					ans[cnt][1] = i;
					ans[cnt][2] = w;
					ans[cnt][3] = i + 1;
					ans[cnt][4] = w;
					grid[i + 1][w]++;
				}
			}
		}
		else {
			for (ll j = w; j >= 2; j--) {
				if (grid[i][j] % 2 == 1) {
					cnt++;
					ans[cnt][1] = i;
					ans[cnt][2] = j;
					ans[cnt][3] = i;
					ans[cnt][4] = j - 1;
					grid[i][j - 1] ++;
				}
			}
			if (i < h) {
				if (grid[i][1] % 2 == 1) {
					cnt++;
					ans[cnt][1] = i;
					ans[cnt][2] = 1;
					ans[cnt][3] = i + 1;
					ans[cnt][4] = 1;
					grid[i + 1][1]++;
				}
			}

		}
	}
	cout << cnt << endl;
	REP(i, 1, cnt) {
		REP(j, 1, 3) {
			cout << ans[i][j] << " ";
		}
		cout << ans[i][4] << endl;
	}
}

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

int main(){
  int N,A[100];
  bool flag=true;
  cin>>N;
  for(int i=0;i<N;i++){
    cin>>A[i];
    if(A[i]%2==0){
      if(A[i]%3!=0 && A[i]%5!=0){
        flag=false;
        break;
      }
    }
  }
  if(flag)cout<<"APPROVED";
  else cout<<"DENIED";
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define Accepted return 0;
int main()
{
    int a,b,c,d,e,f;
    int i,j,k,l,s,ans1,ans2;
    double maxx,res;
    cin>>a>>b>>c>>d>>e>>f;
    maxx=-1;
    for(i=0;i<=30;i++)
    {
        s=i*a*100;
        if (s>f) break;
        for(j=0;j<=30;j++)
        {
            s=i*a*100+j*b*100;
            if (s>f) break;
            for(k=0;k<=3000;k++)
            {
                s=i*a*100+j*b*100+c*k;
                if (s>f) break;
                for(l=0;l<=3000;l++)
                {
                    s=i*a*100+j*b*100+c*k+d*l;
                    if (s>f) break;
                    if ((i*a+j*b)*e<(c*k+d*l)) continue;
                    res=(double)(c*k+d*l)*100.0/(i*a*100+j*b*100);
                    if (res>maxx)
                    {
                        maxx=res;
                        ans1=i*a*100+j*b*100+c*k+d*l;
                        ans2=c*k+d*l;
                    }
                }
            }
        }
    }
    cout<<ans1<<" "<<ans2<<endl;
    Accepted
}

Measured memory_bytes: 256