akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

if __name__ == "__main__":
    S = list(map(int,list(input())))
    K = int(input())
    if 1 not in S:
        print(S[0])
        exit()
    else:
        for i in range(K):
            if S[i] != 1:
                print(S[i])
                exit()
        print(1)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
const long long mod = 998244353;
struct node{
	int x;
	int y;
}no[205];
long long Qpow(long long x,int n)
{
	long long ans=1;
	while(n)
	{
		if(n&1)
			ans=(ans*x)%mod;
		x=(x*x)%mod;
		n=n>>1;
	}
	return ans;
}
int main()
{
	int n;
	scanf("%d",&n);
	long long ans=Qpow(2,n)-1-n;
	for(int i=0;i<n;i++)
		scanf("%d%d",&no[i].x,&no[i].y);
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			int sum=0;
			for(int k=j+1;k<n;k++)
				if ((no[j].x-no[i].x) * (no[k].y-no[j].y) == (no[k].x-no[j].x) * (no[j].y-no[i].y)) 
					sum++;
			ans=(ans-Qpow(2,sum)+mod)%mod;
		}	
	}	
	printf("%lld\n",ans%mod); 
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
#define rep(i, n) for(ll i = 0;i < n;i++)
#define all(i) i.begin(), i.end()
template<class T, class U> bool cmax(T& a, U b) { if (a<b) {a = b; return true;} else return false; }
template<class T, class U> bool cmin(T& a, U b) { if (a>b) {a = b; return true;} else return false; }

template<class T>
struct CumulativeSum {
  vector<T> v;

  CumulativeSum(size_t n) : v(n+1) {};
  CumulativeSum(vector<T> v_) : v(v_) {
    v.push_back(T());
  };

  void add(size_t i, T x) {
    v[i] += x;
  }

  // O(N)
  void build() {
    for (size_t i = v.size()-1; i > 0; i--)
      v[i-1] += v[i];
  }

  // O(1) sum [l, r]
  T sum(size_t l, size_t r) const {
    return v[l]-v[r+1];
  }

  // O(1) sum [0, r]
  T sum(size_t r) const {
    return sum(0, r);
  }
};

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

  ll n;
  cin >> n;
  vl a(n);
  rep(i, n) {
    cin >> a[i];
  }

  sort(a.rbegin(), a.rend());
  CumulativeSum<ll> cs(a);
  cs.build();

  ll ans = 1;
  rep(i, n-1) {
    if (a[i] <= 2*cs.sum(i+1, n-1)) {
      ans++;
    } else {
      break;
    }
  }
  cout << ans << endl;
}


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

typedef long long ll;

#define        optimize           ios::sync_with_stdio(0); cin.tie(0);
#define PI    acos(-1.0)
#define pb push_back
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define RESET(a, b) memset(a, b, sizeof(a))
#define pii pair <int, int>
#define gcd(a, b) __gcd(a, b)
#define min3(a, b, c) min(c, min(a, b))
#define max3(a, b, c) max(c, max(a, b))

#define        MX        3005
string str1, str2;

int dp[MX][MX];

string LCS()
{
    int n = str1.size(), m = str2.size();

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){

        if(str1[i - 1] == str2[j - 1])
            dp[i][j] = dp[i - 1][j - 1] + 1;
        else
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    int i = n, j = m;
    string ans;
    while(dp[i][j]){
        if(dp[i][j] == dp[i-1][j]) i--;

        else if(dp[i][j] == dp[i][j-1]) j--;

        else{
            ans += str1[i-1];
            i--, j--;
        }
    }

    reverse(ans.begin(), ans.end());
    return ans;
}
int main()
{
    cin>>str1>>str2;

    cout<<LCS()<<endl;
}


Measured memory_bytes: 38872
#include "bits/stdc++.h"

using namespace std;

// Molecule := Atom | Atom Number | (Atom) Number | Molecule | Molecule
// Atom := CapitalLetter | CapitalLetter SmallLetter
// Number := 2 | 3 | ... | 99
// CapitalLetter := A | B | ... | Z
// SmallLetter := a | b | ... | z

map<string, int> w;
string s;
int pos;
bool err = false;

int number()
{
    if (err)
        return 0;
    //cerr << "number " << pos << endl;
    int ret = 0;
    while (pos < (int)s.size() && isdigit(s[pos]))
    {
        ret *= 10;
        ret += s[pos] - '0';
        pos++;
    }
    return ret;
}

int atom()
{
    if (err)
        return 0;
    //cerr << "atom " << pos << endl;
    string m = "";
    char c1 = s[pos];
    pos++;
    m += c1;
    if (pos < (int)s.size() && 'a' <= s[pos] && s[pos] <= 'z')
    {
        m += s[pos];
        pos++;
    }
    //cerr << m << endl;
    if (w.find(m) == w.end())
    {
        err = true;
    }
    return w[m];
}

int molecule()
{
    if (err)
        return 0;
    //cerr << "molecule " << pos << endl;
    int ret = 0;
    while (pos < (int)s.size() && s[pos] != ')')
    {
        if (err)
            return 0;
        if (s[pos] == '(')
        {
            pos++; // (
            int m = molecule();
            pos++; // )
            int num = number();
            ret += m * num;
        }
        else
        {
            int a = atom(), num = 1;
            if (pos < (int)s.size() && isdigit(s[pos]))
            {
                num = number();
            }
            ret += a * num;
        }
    }
    return ret;
}

int main()
{
    while (cin >> s, s != "END_OF_FIRST_PART")
    {
        int a;
        cin >> a;
        w[s] = a;
    }
    while (cin >> s, s != "0")
    {
        err = false;
        pos = 0;
        int ret = molecule();
        if (err)
            cout << "UNKNOWN" << endl;
        else
            cout << ret << endl;
    }
}



Measured memory_bytes: 3076
n,m,x = map(int, input().split())
books = [[*map(int, input().split())] for _ in range(n)]
ans = inf = 10**18
for bit in range(1<<n): #  [0,(2^N)-1] combination full search
    cost = 0
    skill = [0]*m
    for book in range(n): # [0,N-1] book no.
        if(bit>>book & 1): # buy
            cost += books[book][0] # cost get
            skill = [*map(lambda x,y: x+y, skill, books[book][1:])] # skill get
    if min(skill) >= x: ans = min(ans, cost) # skill check
if ans == inf: ans = -1 # exist?
print(ans)


Measured memory_bytes: 9200
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);++(i))
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);++(i))
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);--(i))
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);--(i))
#define each(i, a) for(auto &i : a)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
#define out(y,x) ((y) < 0 || h <= (y) || (x) < 0 || w <= (x))
#define line cout << "------------------------\n" 
#define ENDL(i,n) ((i) == (n) - 1 ? "\n" : " ")
#define stop system("pause") //comment out this on AOJ.
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10; //1e-9?
constexpr ld pi = 3.1415926535897932;
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; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }

int main() {
    init();

    int n; cin >> n;
    string s; cin >> s;
    int ans = 0;
    FOR(i, 0, n - 2)if (s.substr(i, 3) == "ABC")++ans;
    cout << ans << "\n";
}

Measured memory_bytes: 256
import java.io.IOException;
import java.util.Scanner;

public class Main{

	public static void main(String[] args) throws IOException {
		Scanner scan = new Scanner(System.in);
		String str = scan.nextLine();
		char charArray[] = str.toCharArray();
		for (int i = charArray.length - 1;i >= 0 ; i--) {
			System.out.print(charArray[i]);
			
		}
		System.out.println();
		
	}
	
}

Measured memory_bytes: 17116
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<string>
#include<cstring>
#include<iomanip>
using namespace std;
typedef long long lng;
typedef unsigned long long ulng;

#define pb push_back
#define SZ(a) int((a).size())
#define ALL(a) (a).begin(), (a).end()
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORD(i,b,a) for(int i=(b); i>=(a); --i)
#define REP(i,n) FOR(i,0,n-1)
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end()) // <a> must be sorted in advance

lng power(lng b, lng e) {lng sol=1; while(e>0) {if(e&1) {sol=sol*b;} e>>=1; b*= b;} return sol;}



int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, b;
    cin >> a >> b;
    if(b == 100) a *= 1000;
    else if(b >= 10) a *= 100;
    else a *= 10;
    int s = a+b;
    FOR(i, 1, 999) {
        if(s == i*i) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;

int main() 
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int a, b; cin >> a >> b;

  cout <<  (a + b + 1) / 2 << endl;
  
  return 0;
}



Measured memory_bytes: 256
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.IntStream;

public class Main {

  public static void main(String[] args) {
    resolve(System.in, System.out);
  }

  static void resolve(InputStream is, PrintStream pw) {
    Scanner sc = new Scanner(is);
    int n = Integer.parseInt(sc.next());
    int[] x = new int[n];
    int min = 100;
    int max = 1;
    for (int i = 0; i < n; i++) {
      int xi = Integer.parseInt(sc.next());
      min = Math.min(min, xi);
      max = Math.max(max, xi);
      x[i] = xi;
    }
    pw.println(
      IntStream.rangeClosed(min, max)
        .map(p -> distance(p, x))
        .min()
        .getAsInt()
    );
  }

  static int distance(int p, int[] x) {
    return Arrays.stream(x)
      .map(xi -> (xi - p) * (xi - p))
      .sum();
  }
}


Measured memory_bytes: 28116
#include <bits/stdc++.h>
using namespace std;
int main(){
	int N; cin >> N; 
	int W[110] = {}; int S[110] = {}; 
	for(int i = 1; i <= N; i++){
		cin >> W[i]; S[i] = S[i-1] + W[i]; 
	}
	int ans = 1145141919; 
	for(int i = 1; i <= N; i++){
		ans = min(ans, abs(S[N] - 2 * S[i])); 
	}
	cout << ans << endl; 
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define Senky_Bansal ios_base::sync_with_stdio(false);
#define IIIT_ALLAHABAD    cin.tie(NULL);cout.tie(NULL);
using namespace std;
int main()
{
    Senky_Bansal
    IIIT_ALLAHABAD
    ll n,m,c;
  cin>>n>>m>>c;
  ll b[m];
  for(int i=0;i<m;i++)
    cin>>b[i];
  ll final=0;
  for(int i=0;i<n;i++)
  {
    ll ans=c;
    for(int j=0;j<m;j++)
    {
      ll a;
      cin>>a;
      ans+=a*b[j];
    }
    if(ans>0) final++;
  }
  cout<<final<<endl;
}


Measured memory_bytes: 256
import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T
import qualified Data.Vector.Unboxed as VU
import qualified Data.IntMap as IM

main :: IO ()
main = do
  [n, k] <- map unsafeTextToInt . T.words <$> T.getLine :: IO [Int]
  as <- VU.map pred . unsafeTextToVectorInt <$> T.getLine :: IO (VU.Vector Int)
  let
    (start, period) = go 0 0 IM.empty :: (Int, Int)
      where
        go :: Int -> Int -> IM.IntMap Int -> (Int, Int)
        go l i m | Just s <- IM.lookup i m = (s, l - s)
                 | otherwise               = go (succ l) (as VU.! i) (IM.insert i l m)
    pos :: Int -> Int
    pos = go 0
      where
        go :: Int -> Int -> Int
        go i 0 = i
        go i l = go (as VU.! i) (pred l)
  print . succ . pos $ if k < start then k else start + (k - start) `mod` period

unsafeTextToVectorInt :: T.Text -> VU.Vector Int
unsafeTextToVectorInt = VU.unfoldr next
  where
    next :: T.Text -> Maybe (Int, T.Text)
    next s | T.null s  = Nothing
           | otherwise = Just . either undefined (T.stripStart <$>) . T.signed T.decimal $ s
{-# INLINE unsafeTextToVectorInt #-}

unsafeTextToInt :: T.Text -> Int
unsafeTextToInt s = case T.signed T.decimal s of
  Right (n, _) -> n
{-# INLINE unsafeTextToInt #-}


Measured memory_bytes: 48680
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int N = scan.nextInt();
        long[] A = new long[N];
        for (int i = 0; i < N; i++) {
            A[i] = scan.nextLong();
        }
        long ans = solve(A, 0, N-1, 1, 1) + A[0] + A[N-1];
        System.out.println(ans);
    }
    public static long solve(long[] A, int left, int right, int c_l, int c_r) {
        if (left + 1 == right) {
            return 0;
        }
        long ans = Long.MAX_VALUE;
        for (int i = left + 1; i < right; i++) {
            ans = Math.min(ans, solve(A, left, i, c_l, c_l + c_r) + solve(A, i, right, c_l + c_r, c_r) + (c_l + c_r) * A[i]);
        }
        return ans;
    }
}


Measured memory_bytes: 24020
N = int(input())
F = [[[0 for k in range(2)] for j in range(5)] for i in range(N)]

for i in range(N):
    l = [int(_) for _ in input().split()]
    for j in range(10):
        if j % 2 == 0:
            F[i][j//2][0] = l[j]
        else:
            F[i][(j-1)//2][1] = l[j]

P = [0] * N

for i in range(N):
    P[i] = [int(_) for _ in input().split()]

res = -10000000000

for u in range(1<<10):
        if u != 0:
            tmp = 0
            for i in range(N):
                cnt = 0
                for j in range(5):
                    for k in range(2):
                        if F[i][j][k] & ((u>>(2*j+k))&1):
                            cnt += 1
                tmp += P[i][cnt]
            res = max(res,tmp)

print(res)

Measured memory_bytes: 3064
#include <iostream>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)

int main(void)
{
	int N;
	cin >> N;
	int ans = 1;
	if(N == 1){
		cout << ans << endl;
		return 0;
	}

	int a, b;
	cin >> a;
	int dir = 0;
	int count_dir = 0;
	rep(i, N){
		cin >> b;
		if(b == a) continue;
		if(a < b){
			if(count_dir == 0) count_dir = -1;
			if(count_dir == 1 && dir == -1) ans++, count_dir = 0;
			dir = 1;
		}else{
			if(count_dir == 0) count_dir = 1;
			if(count_dir == -1 && dir == 1) ans++, count_dir = 0;
			dir = -1;
		}
		a = b;
	}
	cout << ans << endl;
	return 0;
}


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

using namespace std;

long long A, B, C, X, Y;
long long price;

int main()
{
	scanf("%lld %lld %lld %lld %lld", &A, &B, &C, &X, &Y);
	long long tempAns1 = (X * A) + (Y * B);
	long long tempAns2 = 2 * max(X, Y) * C;
	long long tempAns3 = 2 * min(X, Y) * C;
	if(max(X, Y) == X) {
		tempAns3 += (X - Y) * A;
	}
	else
	{
		tempAns3 += (Y - X) * B; 
	}
	// cerr << tempAns1 << " " << tempAns2 << " " << tempAns3 << " ";
	long long finalAns = min(tempAns1, min(tempAns3, tempAns2));
	printf("%lld\n", finalAns);
	
	return 0;
}
/*
	Powered by Buggy Plugin
*/


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=(a),_ed=(b);i<=_ed;++i)
#define DREP(i,a,b) for(int i=(a),_ed=(b);i>=_ed;--i)
#define mp(x,y) make_pair((x),(y))
#define sz(x) (int)(x).size()
#define pb push_back
typedef long long ll;
typedef pair<int,int> pii;
inline int read(){
    register int x=0,f=1;register char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
    while(isdigit(ch)){x=x*10+(ch^'0');ch=getchar();}
    return f?x:-x;
}

const int N=1e5+5,mod=1e9+7;
int n,tr[N][3],f[N],sum[N];char s[N];
inline void inc(int& x,int y){x=x+y<mod?x+y:x+y-mod;}

/*
  s可以变成t当且仅当
  - t可以在s上分段表示出来(每个t中字符和s的每一段mod3同余,且s最后一段不匹配的mod3=0)
  - s存在两个相邻字符相同
  分段表示可以考虑贪心,用最短的去匹配(不算重)
 */
  
int main(){
	// freopen("in.in","r",stdin);
	scanf("%s",s+1);n=strlen(s+1);
	int flg=0;
	REP(i,2,n)if(s[i]==s[i-1])flg=1;
	if(!flg)return puts("1"),0;
	REP(i,1,n)sum[i]=(sum[i-1]+(s[i]=='a'?1:2))%3;
	REP(i,0,2)tr[n][i]=n+1;
	DREP(i,n-1,0){
		REP(j,0,2)tr[i][j]=tr[i+1][j];
		tr[i][sum[i+1]]=i+1;
	}
	f[0]=1;int ans=0;
	REP(i,0,n){
		REP(j,1,2)inc(f[tr[i][(sum[i]+j)%3]],f[i]);
		if(sum[i]==sum[n]&&i)inc(ans,f[i]);
	}
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 2304
#include<stdio.h>
int main()
{
   
     int num;
    scanf("%d", &num);
	long ans = 0;
   int i=0;
  int check = 0;
  
  for(i=0;i<num*1.08;i++){
	ans = i*1.08;
    check = ans;
  	if(check == num){
		printf("%d",i);
      return 0;
    }
  }
	printf(":(");
    return 0;
}

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

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<vector<vector<bool>>> vvvb;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<double> vd;
typedef vector<vd> vdd;

#define FOR(i,x,y) for(ll i=(ll)x; i<(ll)y; ++i)
#define REP(i,y) FOR(i, 0, y)
#define RFOR(i,x,y) for(ll i=(ll)x; i>=(ll)y; --i)
#define RREP(i,x) RFOR(i, x, 0)
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define debug_print(x...) cerr << "line " << __LINE__ << " : "; debug_print_in(x);

template <typename First>
void debug_print_in(First first){
  cerr << first << endl;
  return;
}

template <typename First, typename... Rest>
void debug_print_in(First first, Rest... rest){
  cerr << first << " ";
  debug_print_in(rest...);
  return;
}

void IN(void){
  return;
}

template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){
  cin >> first;
  IN(rest...);
  return;
}

template <typename First>
void OUT(First first){
  cout << first << endl;
  return;
}

template <typename First, typename... Rest>
void OUT(First first, Rest... rest){
  cout << first << " ";
  OUT(rest...);
  return;
}

template<class t, class u> void chmax(t&a,u b){if(a<b)a=b;};
template<class t, class u> void chmin(t&a,u b){if(a>b)a=b;};
int popcount(int t){return __builtin_popcount(t);} //GCC
int popcount(ll t){return __builtin_popcountll(t);} //GCC

template <typename T>
void vec_print(vector<T> VEC){
  REP(i, VEC.size()){
    cerr << VEC[i] << " ";
  }
  cerr << endl;
};

template <typename T>
void mat_print(vector<vector<T> > MAT){
  REP(i,MAT.size()){
    REP(j,MAT[i].size()){
      cerr << MAT[i][j] << " ";
    }
    cerr << endl;
  }
};

constexpr int INF = (1<<30);
constexpr ll INFLL = 1LL<<62;
constexpr long double EPS = 1e-12;
constexpr ll MOD = (ll)((1E+9)+7);

ll N;
vpll AP;

vvll dp;

ll search(ll left, ll right, ll index){
  if(left<0 || left>=N) return 0;
  if(right<0 || right>=N) return 0;
  if(index>=N) return 0;
  if(left>right) return 0;
  if(dp[left][right]>=0) return dp[left][right];

  dp[left][right] = 0;
  chmax(dp[left][right], search(left+1, right, index+1) + AP[index].first*abs(AP[index].second-left));
  chmax(dp[left][right], search(left, right-1, index+1) + AP[index].first*abs(AP[index].second-right));

  return dp[left][right];
}

int main(){
  cin.tie(0); // cut the cin and cout (default, std::flush is performed after std::cin)
  ios::sync_with_stdio(false); // cut the iostream and stdio (DON'T endl; BUT "\n";)

  IN(N);
  AP.resize(N);
  dp.resize(N, vll(N, -1));
  REP(i,N){
    IN(AP[i].first);
    AP[i].second = i;
  }

  sort(ALL(AP));
  reverse(ALL(AP));

  OUT(search(0, N-1, 0));

  return 0;
}

Measured memory_bytes: 34624
#include <iostream>
#include <string>
#include <cmath>
#define rep(i,n) for (int i = 0; i<(n); i++)
using namespace std;
using P = pair<int,int>;
#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>
#define rep(i,n) for (int i = 0; i<(n); i++)
using namespace std;
using P = pair<int,int>;
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <set>


int main() {
    int a, b;
    cin >> a>>b;
    cout << (3*a+b)/2;
    return 0;
}

Measured memory_bytes: 3636
#include "bits/stdc++.h"
using namespace std;
#define INF 1e9
#define rep(i, n) for(int i = 0; i < n; i++)
#define ALL(x) (x).begin(), (x).end()  //昇順
#define RALL(x) (x).rbegin(), (x).rend() // 降順
const long long mod = 1e9+7;
typedef priority_queue<int> PQ;
typedef vector<long long> VL;
typedef vector<int> VI;  // VI a(n);
typedef vector<string> VS;  
typedef vector<char> VC; 
typedef vector<VS> VSS;
typedef vector<VC> VCC;    
typedef vector<VI> VVI;   // VVI a(n,vector<int>(m)) n * m 
typedef vector<VL> VVL;
typedef pair<int, int> PII;
typedef map<int, int> MP;   //MP a;
typedef vector<pair<int, int> > PS;
typedef long long ll;  //ll とdoubleは違う
template <class T>  // chmax(max, a);
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T> //chmin(min,a)
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
template<typename T>   // operator << (cout,a);
ostream& operator << (ostream& os, vector<T>& v) {
    os << "{";
    rep(i, (int)v.size()) { os << v[i] << (i < v.size() - 1 ? ", " : ""); }
    os << "}";
    return os;
}

ll max=-1000000000,min=1e9+1;

int main(){
    ll x=0,y=0,n,m,h,k,w,sum=0,sum2=0;
    string s;
    cin >> n;
    VI a(100000);
    VI ans(100000);

    rep(i,n){
        cin >> a[i];
        sum += a[i];
	}
    for(int i=1; i<n-1;i+=2){
        sum2 += a[i];
    } 
    ans[0] = sum - 2*sum2;
    for(int i=0; i<n;i++){
        ans[i+1] = 2*a[i]-ans[i];
    }
    
    rep(i,n){
        if(i==n-1)
            cout << ans[i];
        else cout << ans[i] << " ";
    }
    return 0;
}

Measured memory_bytes: 2048
<?php
  
  list($n, $a, $b) = explode(" ", trim(fgets(STDIN)));

  $ans = (int)($n/($a+$b))*$a;
  $mod = $n%($a+$b);
  if($mod <= $a){
    $ans+=$mod;
  }else{
    $ans+=$a;
  }
  echo $ans;
  

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

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


    int W,H;
    cin>>H>>W;
    int dp[H][W];
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            int tile;
            if(cin>>tile,tile==0){
                dp[i][j]=(j?dp[i][j-1]:0)+1;
            }else{
                dp[i][j]=0;
            }
        }
    }
    int ans=0;
    typedef pair<int,int> P;
    stack<P,vector<P>> S;
    for(int j=0;j<W;j++){
        for(int i=0;i<H;i++){
            if(S.empty()){
                S.emplace(dp[i][j],i);
                continue;
            }
            P p = S.top();
            if(p.first==dp[i][j]){
                continue;
            }
            if(p.first<dp[i][j]){
                S.emplace(dp[i][j],i);
                continue;
            }
            while(!S.empty()){
                ans=max(ans,p.first*(i-p.second));
                S.pop();
                if(S.empty()){
                    S.emplace(dp[i][j],p.second);
                    break;
                }
                if(S.top().first>=dp[i][j]){
                    p=S.top();
                    continue;
                }else{
                    S.emplace(dp[i][j],p.second);
                    break;
                }
            }
        }
        while(!S.empty()){
            P p = S.top(); S.pop();
            ans=max(ans,p.first*(H-p.second));
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 10832
n,w = map(int,input().split())
w_ls, v_ls = [0] * n, [0] * n
for i in range(n):
    w_ls[i], v_ls[i] = map(int,input().split())
V = sum(v_ls)
dp = [[float("inf")] * (V+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
    for j in range(V+1):
        if j - v_ls[i] >= 0:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j-v_ls[i]] + w_ls[i])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

ans = 0
for j in range(V+1):
    if dp[n][j] <= w:
        ans = j

print(ans)

Measured memory_bytes: 311888
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef long long int int64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

int root(int *u,int x){
  if(u[x]==x) return x;
  return u[x]=root(u,u[x]);
}

int same(int *u,int x,int y){
  return root(u,x)==root(u,y);
}

void unite(int *u,int x,int y){
  x=root(u,x);
  y=root(u,y);
  if(x==y) return;
  u[x]=y;
}

void run(void){
  int n,q;
  scanf("%d%d",&n,&q);
  int *u=(int *)malloc(sizeof(int)*n);
  int i;
  for(i=0;i<n;i++) u[i]=i;
  while(q--){
    int c,x,y;
    scanf("%d%d%d",&c,&x,&y);
    if(c==0){
      unite(u,x,y);
    } else {
      printf("%d\n",same(u,x,y));
    }
  }
}

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



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

using namespace std;

using ll = long long;

const ll inf = 1000000000000000000;

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

	int n, K;
	cin >> n >> K;

	vector<int> h;
	h.resize(n);

	for(int i = 0; i < n; ++i) {
		cin >> h[i];
	}

	vector<vector<vector<ll> > > dp;

	dp.resize(n + 1);

	for(int i = 0; i < n + 1; ++i) {
		dp[i].resize(n + 1);

		for(int j = 0; j < n + 1; ++j) {
			dp[i][j].assign(n + 1, inf);
		}
	}

	dp[0][0][0] = 0;

	vector<int> v = h;

	v.emplace_back(0);

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

	v.erase(unique(v.begin(), v.end()), v.end());

	vector<int> id;
	id.resize(n);

	for(int i = 0; i < n; ++i) {
		id[i] = lower_bound(v.begin(), v.end(), h[i]) - v.begin();
	}

	for(int i = 0; i < n; ++i) {
		vector<vector<ll> > pre;
		pre.resize(n + 1);

		for(int i = 0; i < n + 1; ++i) {
			pre[i].resize(n + 1);
		}
		
		vector<vector<ll> > suf;
		suf.resize(n + 1);

		for(int i = 0; i < n + 1; ++i) {
			suf[i].resize(n + 1);
		}
		
		for(int j = 0; j <= K; ++j) {
			pre[j][0] = dp[i][j][0] - v[0];

			for(int k = 0; k + 1 < v.size(); ++k) {
				pre[j][k + 1] = min(pre[j][k], dp[i][j][k + 1] - v[k + 1]);
			}
		}

		for(int j = 0; j <= K; ++j) {
			suf[j][(int)v.size() - 1] = dp[i][j][(int)v.size() - 1];
			
			for(int k = (int)v.size() - 2; k >= 0; --k) {
				suf[j][k] = min(suf[j][k + 1], dp[i][j][k]);
			}
		}
		
		for(int j = 0; j <= K; ++j) {
			for(int k = 0; k < v.size(); ++k) {
				dp[i + 1][j][id[i]] = min(dp[i + 1][j][id[i]], dp[i][j][k] + max(0, v[id[i]] - v[k]));
			} 
	
			if(j < K) {
				for(int k = 0; k < v.size(); ++k) {
					dp[i + 1][j + 1][k] = min(dp[i + 1][j + 1][k], v[k] + pre[j][k]);
					dp[i + 1][j + 1][k] = min(dp[i + 1][j + 1][k], suf[j][k]);
				}
			}
		}
	}

	cout << *min_element(dp[n][K].begin(), dp[n][K].end()) << '\n';

	return 0;

}

Measured memory_bytes: 219796
#include "bits/stdc++.h"
#define REP(i, n) for(int i = 0; i < int(n); i++)
#define FOR(i,n,m) for(int i = int(n); i < int(m); i++)
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 6;
const ll LLINF = 1e18 + 1;

int main() {
    int r; cin >> r;
    cout << r * r << endl;
    return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>
#include <iterator>
 
using namespace std;
 
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
 
#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)c.size())

typedef unsigned long long ull;
const int INF = (int)1e8;

class UnionFind{
	int n;
	vector<int> par;
	vector<int> rank;
public:
	UnionFind(){ }
	UnionFind(int size){ reset(size); }

	void reset(int size){
		n = size;
		par.resize(size);
		rank.resize(size);
		for(int i = 0; i < size; i++) par[i] = i,rank[i] = 0;
	}

	int find(int x){
		if(par[x] == x) return x;
		return par[x] = find(par[x]);
	}

	void unite(int x,int y){
		x = find(x),y = find(y);
		if(x == y) return ;
		if(rank[x] < rank[y]){
			par[x] = y;
		}else{
			par[y] = x;
			if(rank[x] == rank[y]) rank[x]++;
		}
		n--;
	}

	bool same(int x,int y){return find(x) == find(y);}

	int size() {return n;}
};

int main(){
	int n,m;
	while(cin>>n>>m,n||m){
		UnionFind u(n);
		vector<pair<int,Pii> > v;
		FOR(i,m){
			int a,b,c; cin>>a>>b>>c;
			v.push_back(make_pair(c,Pii(a,b)));
		}
		int ans = 0;
		sort(v.begin(),v.end());
		FOR(i,m){
			if(u.size() == 1) break;
			int cost = v[i].first;
			Pii p = v[i].second;
			if(!u.same(p.first,p.second)){
				ans += cost;
				u.unite(p.first,p.second);
			}
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1204
// https://atcoder.jp/contests/dp/tasks/dp_d

#include <iostream>
#include <cstring>

using namespace std;
using ll = long long;

int main() {
    int num, weight;
    cin >> num >> weight;

    int w[num], v[num];
    for (int i = 0; i < num; ++i) {
        cin >> w[i] >> v[i];
    }

    ll dp[num + 1][weight + 1];

    memset(dp, 0, sizeof(dp));

    for (int i = 0; i <= weight; ++i) {
        dp[0][i] = 0;
    }

    for (int i = 1; i <= num; ++i) {
        for (int j = 0; j <= weight; ++j) {
            int targetValue = v[i - 1];
            int targetWeight = w[i - 1];

            if (j - targetWeight < 0) {
                dp[i][j] = dp[i - 1][j];
                continue;
            }

            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - targetWeight] + targetValue);
        }
    }

    cout << dp[num][weight] << endl;
    return 0;
}

Measured memory_bytes: 79104
#include <bits/stdc++.h>
using namespace std;
int main() {
 int a, b,c;
  cin >> a >> b >>c;
  int d = b/a;
  int e = c/a;
  int f = b%a;
  int g = c%a;
  if(a==1||f==0||g==0){
    cout << "OK" <<endl;
  }
    else if(e==d){
      cout << "NG" <<endl;
    }
  else{
    cout << "OK" <<endl;
  }
}


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


public class Main {

	private static Scanner sc;
	private static Printer pr;

	private static void solve() {
		char[] s = sc.next().toCharArray();

		int cnt = 0;
		for (char c : s) {
			if (c == 'o') {
				cnt++;
			}
		}

		pr.println(700 + cnt * 100);
	}

	// ---------------------------------------------------
	public static void main(String[] args) {
		sc = new Scanner(INPUT == null ? System.in : new ByteArrayInputStream(INPUT.getBytes()));
		pr = new Printer(System.out);

		solve();

//		pr.close();
		pr.flush();
//		sc.close();
	}

	static String INPUT = null;

	private static class Printer extends PrintWriter {
		Printer(OutputStream out) {
			super(out);
		}
	}
}


Measured memory_bytes: 23252
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  double ans=0;
  cin>>n;
  for(int i=0;i<n;i++){
    double x;
    string u;
    cin>>x>>u;
    if(u=="JPY"){ans+=x;}
    else{ans+=x*380000.0;}
  }
  cout<<ans;
}


Measured memory_bytes: 256
#include <math.h>

#include <algorithm>
#include <bitset>
#include <iostream>
#include <sstream>
#include <vector>

using namespace std;

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> a(N, 0);
  for (int i = 0; i < K; i++) {
    int d;
    cin >> d;
    for (int j = 0; j < d; j++) {
      int a_j;
      cin >> a_j;
      a.at(a_j - 1) += 1;
    }
  }
  int ans = 0;
  for (int i = 0; i < N; i++) {
    if (a.at(i) == 0) {
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}


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

int main(){
    int n=1e5;
    vector<int> like;
    vector<bool> is_prime(n + 1, 1);
    for (int p = 2; p <= n; p++) {
        if (!is_prime[p]) continue;
        for (int k = 2*p; k <= n; k += p) is_prime[k] = false;
        if(is_prime[(p+1)/2]) like.push_back(p);
    }

	int q;
	cin >> q;
    for(int i=0; i<q; i++){
	    int l, r;
        cin >> l >> r;
        if(l==1) l=3;
        int cnt=upper_bound(like.begin(), like.end(), r)-lower_bound(like.begin(), like.end(), l);
        cout << cnt << endl;
    }
}

Measured memory_bytes: 640
#include <iostream>
#include <stdio.h>
using namespace std;

int main()
{
    int cnum=-1;
    int i;
    char lla;
    bool success =true;
    for (i=0; ; i++)
    {
        lla=getchar();
        if (lla=='\n'||lla==' ')
            break;
        if (i==0)
        {
            if (lla!='A')
                success=false;
        }
        if (lla>='A' &&lla<='Z')
        {
            if (lla!='A' &&lla!='C')
                success =false;
        }
        if (lla == 'C')
        {
            if (cnum!=-1)
                success =false;
            else
                cnum=i;
        }
    }
    if (cnum <= 1 ||cnum==i-1)
            success=false;
    //cout<<cnum<<' '<<i<<endl;
    if (success)
    cout << "AC" << endl;
    else
        cout<<"WA"<<endl;
    return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
MOD = 10**9 + 7

N, M = map(int, input().split())
broken_floors = set(int(input()) for _ in range(M))
dp = [0]*(N+2)
dp[1] = 1

for i in range(1, N+1):
    if i not in broken_floors:
        dp[i+1] = (dp[i] + dp[i-1]) % MOD

print(dp[-1])

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

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

typedef long long ll;
using namespace std;

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

  int N;
  cin >> N;
  vector<ll> A(N);
  ll ans = 0;
  ll a;
  REP(i, N) {
    cin >> a;
    ans += a - 1;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int a[4],b[4];
    int asum=0;
    int bsum=0;
    for (int i=0;i<4;++i){
        cin>>a[i];
        asum+=a[i];
    }
    for (int i=0;i<4;++i){
        cin>>b[i];
        bsum+=b[i];
    }
    if(asum>bsum){
        cout << asum<<endl;
    }
    else{
        cout <<bsum<< endl;
    }
    return 0;

}



Measured memory_bytes: 3104
#include <bits/stdc++.h>
using namespace std;
using lint     = long long;
const lint inf = 1LL << 60;
const lint mod = 1000000007;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    lint n, k;
    cin >> n >> k;
    n %= k;
    cout << min(n, abs(n - k)) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1000000000
#define LINF 1000000000000000000
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define bit(n) (1LL<<(n))
using namespace std;

typedef pair<int, int> P;
typedef pair<long long, long long> LLP;

int main() {

    int N;

    vector<int> A(3);
    cin >> N >> A[0] >> A[1] >> A[2];
    vector<string> s(N);
    rep(i,N) cin >> s[i];
    vector<int> c(N);
    rep(i,N) {
        if (s[i] == "AB") c[i] = 0;
        else if (s[i] == "BC") c[i] = 1;
        else c[i] = 2;
    }

    vector<int> ans(N);

    rep(k,N) {
        int i = c[k];
        int j = (i + 1) % 3;
        if (A[i] == 0 && A[j] == 0) {
            cout << "No" << endl;
            return 0;
        }
        if (A[i] == 0) {
            A[i]++;
            A[j]--;
            ans[k] = i;
        } else if (A[j] == 0) {
            A[j]++;
            A[i]--;
            ans[k] = j;
        } else {
            if (A[0] + A[1] + A[2] == 2 && A[i] + A[j] == 2 && k < N - 1 && c[k] != c[k + 1]) {
                if ((c[k] + 1) % 3 == c[k + 1]) {
                    A[j]++;
                    A[i]--;
                    ans[k] = j;
                } else {
                    A[i]++;
                    A[j]--;
                    ans[k] = i;
                }
            } else {
                if (A[i] == 1) {
                    A[i]++;
                    A[j]--;
                    ans[k] = i;
                } else {
                    A[j]++;
                    A[i]--;
                    ans[k] = j;
                }
            }
        }
    }
    cout << "Yes" << endl;
    rep(i,N) {
        if (ans[i] == 0) cout << "A" << endl;
        else if (ans[i] == 1) cout << "B" << endl;
        else cout << "C" << endl;
    }
    
    return 0;
}

Measured memory_bytes: 7196
import java.util.*;
 
public class Main{
  public static void main (String args[]){
    Scanner sc = new Scanner(System.in);
    int num = sc.nextInt();
    String ans = "No";
    
    if (num <= 81){
      for (int dan = 1; dan < 10; dan++){    
        if (num <= 9*dan && num%dan == 0) {
        ans = "Yes";
        break;
        }
      }
    } 
    System.out.println(ans);
  }
}

Measured memory_bytes: 23252
/*
AizuOnline A0025
Hit and Blow
*/
#include <stdio.h>



main()
{
  int a[4];
  int b[4];
             /*length between centers*/
  int  hit,blow,i,j;
  
     while (4==scanf(" %d %d %d %d",&a[0],&a[1],&a[2],&a[3]) &&
            4==scanf(" %d %d %d %d",&b[0],&b[1],&b[2],&b[3]))
       { hit=0;blow=0;
         for(i=0;i<4;i++)
           for(j=0;j<4;j++)
             if(a[i]==b[j])
               {  if(i==j)hit++;
                  else blow++;
               }
                 printf("%d %d\n",hit,blow);
       }
  



return(0);
}

Measured memory_bytes: 0
n = int(input())
L = [int(s) for s in input().split()]

ans = 0
for i in range(n-2):
    Lbc = L[i:i+3]
    Lbs = sorted(Lbc)
    if Lbc[1] == Lbs[1]:
        ans += 1
    else:
        pass
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <cassert>
#include <string>
#include <memory.h>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <set>
#include <map>
#include <cctype>
#include <iomanip>
#include <sstream>
#include <cctype>
#include <fstream>
#include <cmath>
using namespace std;

#define REP2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define REP(i, n) REP2(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
#define ITER(c) __typeof((c).begin())
#define PB(e) push_back(e)
#define FOREACH(i, c) for(ITER(c) i = (c).begin(); i != (c).end(); ++i)
#define MP(a, b) make_pair(a, b)
#define PARITY(n) ((n) & 1)

typedef long long ll;
typedef pair<ll, ll> P;
typedef unsigned int uint;

const uint INF = (uint)1 << 31;
const int sz = 1000010;
uint field[sz];
uint dat[sz * 20];
int R, C, Q;

#define FIELD(r, c) (field[(r) * C + (c)])
#define DAT(kr, kc) (dat[(kr) * (C) * 4 + (kc)])

void build(int lr, int rr, int lc, int rc, int kr, int kc, bool r_axis = true){
  if(rr - lr == 1 && rc - lc == 1){
    DAT(kr, kc) = FIELD(lr, lc);
  }else if((r_axis && rr - lr > 1) || rc - lc == 1){
    assert(rr - lr != 1);
    int mr = (lr + rr) / 2;
    build(lr, mr, lc, rc, kr * 2 + 1, kc, false);
    build(mr, rr, lc, rc, kr * 2 + 2, kc, false);
    DAT(kr, kc) = min(DAT(kr * 2 + 1, kc), DAT(kr * 2 + 2, kc));
    
  }else{
    int mc = (lc + rc) / 2;
    build(lr, rr, lc, mc, kr, kc * 2 + 1, true);
    build(lr, rr, mc, rc, kr, kc * 2 + 2, true);
    DAT(kr, kc) = min(DAT(kr, kc * 2 + 1), DAT(kr, kc * 2 + 2));
  }
}

uint query(int ar, int br, int ac, int bc,
           int lr = 0, int rr = R, int lc = 0, int rc = C,
           int kr = 0, int kc = 0, bool r_axis = true){
  if(rr <= ar || br <= lr || rc <= ac || bc <= lc || rr <= lr || rc <= lc)return INF;
  
  if(ar <= lr && rr <= br && ac <= lc && rc <= bc){
    return DAT(kr, kc);
  }else if((r_axis && rr - lr > 1) || rc - lc == 1){
    int mr = (lr + rr) / 2;
    return min(query(ar, br, ac, bc, lr, mr, lc, rc, kr * 2 + 1, kc, false),
               query(ar, br, ac, bc, mr, rr, lc, rc, kr * 2 + 2, kc, false));
  }else{
    int mc = (lc + rc) / 2;
    return min(query(ar, br, ac, bc, lr, rr, lc, mc, kr, kc * 2 + 1, true),
               query(ar, br, ac, bc, lr, rr, mc, rc, kr, kc * 2 + 2, true));
  }
}

uint naive(int ar, int br, int ac, int bc){
  uint ans = INF;
  REP2(i, ar, br)REP2(j, ac, bc) ans = min(ans, FIELD(i, j));
  return ans;
}

int main(){
  int r1, r2, c1, c2;
  while(scanf("%d%d%d", &R, &C, &Q) != EOF){
    
    REP(r, R)REP(c, C) scanf("%d", &FIELD(r, c));
    if(R > 0 && C > 0) build(0, R, 0, C, 0, 0);
    REP(q, Q){
      scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
      printf("%u\n", query(r1, r2 + 1, c1, c2 + 1));
    }
  }
  return 0;
}

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

int N, X[1 << 18], Y[1 << 18];
char D[1 << 18];

void Rotate() {
	for (int i = 1; i <= N; i++) {
		int cx = Y[i], cy = 200000 - X[i], cz;
		if (D[i] == 'U') cz = 'R';
		if (D[i] == 'R') cz = 'D';
		if (D[i] == 'D') cz = 'L';
		if (D[i] == 'L') cz = 'U';
		X[i] = cx; Y[i] = cy; D[i] = cz;
	}
}

vector<pair<int, char>> V1[1 << 19];
vector<pair<int, char>> V2[1 << 19];

int solve_01() {
	int Answer = (1 << 24);
	for (int i = 0; i <= 500000; i++) V1[i].clear();
	for (int i = 1; i <= N; i++) {
		if (!(D[i] == 'R' || D[i] == 'U')) continue;
		V1[X[i] + Y[i]].push_back(make_pair(X[i], D[i]));
	}
	for (int i = 0; i <= 500000; i++) {
		sort(V1[i].begin(), V1[i].end());
		for (int j = 0; j < (int)V1[i].size() - 1; j++) {
			if (!(V1[i][j].second == 'R' && V1[i][j + 1].second == 'U')) continue;
			Answer = min(Answer, V1[i][j + 1].first - V1[i][j].first);
		}
	}
	return Answer * 10;
}

int solve_02() {
	int Answer = (1 << 24);
	for (int i = 0; i <= 500000; i++) V2[i].clear();
	for (int i = 1; i <= N; i++) {
		if (!(D[i] == 'L' || D[i] == 'R')) continue;
		V2[Y[i]].push_back(make_pair(X[i], D[i]));
	}
	for (int i = 0; i <= 500000; i++) {
		sort(V2[i].begin(), V2[i].end());
		for (int j = 0; j < (int)V2[i].size() - 1; j++) {
			if (!(V2[i][j].second == 'R' && V2[i][j + 1].second == 'L')) continue;
			Answer = min(Answer, V2[i][j + 1].first - V2[i][j].first);
		}
	}
	return Answer * 5;
}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> X[i] >> Y[i] >> D[i];

	int FinalAns = (1 << 24);
	for (int t = 1; t <= 4; t++) {
		int val1 = solve_01(); FinalAns = min(FinalAns, val1);
		int val2 = solve_02(); FinalAns = min(FinalAns, val2);
		Rotate();
	}
	if (FinalAns == (1 << 24)) cout << "SAFE" << endl;
	else cout << FinalAns << endl;
	return 0;
}

Measured memory_bytes: 42740
using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            long[] inputLongArray = Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();
            long N = inputLongArray[0];
            long D = inputLongArray[1];
            int cnt = 0;
            while(true)
            {
                if (D * 2 + 1<N)
                {
                    N -= (D * 2 + 1);
                    cnt++;
                }
                else
                {
                    break;
                }
            }
            if (N != 0)
            {
                cnt += 1;
            }
            Console.WriteLine(cnt);

        }
    }
}
// 文字列の入力
//string s = Console.ReadLine();

// 整数の入力
//long n = long.Parse(Console.ReadLine());

// 文字列配列の入力
//string[] inputStrArray = Console.ReadLine().Split(' ');

// 整数配列の入力
//long[] inputLongArray = Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();


Measured memory_bytes: 13268
#include<iostream>
#include<algorithm>
#include<cstdint>
using namespace std; // 575

int main() {
	int N, A, B;
	static int h[100000];
	cin >> N >> A >> B;
	for (int i = 0;i < N;++ i) cin >> h[i];
	int l = 0, r = 1000000000, d;
	while (d = r - l >> 1) {
		int64_t m = l + d, explosion = 0;
		for (int i = 0;i < N;++ i) explosion += max((int64_t)0, (h[i] - m * B + A - B - 1) / (A - B));
		(explosion > m ? l : r) = m;
	}
	cout << r;
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり
また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー

*/

Measured memory_bytes: 640
if __name__ == '__main__':
    a, b, c, d = map(int, input().split())

    if abs(c - a) <= d:
        print("Yes")
        exit(0)

    if abs(b - a) <= d and abs(c - b) <= d:
        print("Yes")
        exit(0)
    
    print("No")


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,a[200000];
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        a[i]-=i;
    }
    sort(a,a+n);
    long long ans=0;
    for(int i=0;i<n;i++){
        ans+=abs(a[i]-a[n/2]);
    }
    cout<<ans<<endl;
}

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

int A, B, k;

int main(){
    scanf("%d%d%d", &A, &B, &k);
    if(B-A+1 >= k*2){
        for(int i=A; i<=A+k-1; i++){
            printf("%d\n", i);
        }
        for(int i=B-k+1; i<=B; i++){
            printf("%d\n", i);
        }
    }
    else{
        for(int i=A; i<=B; i++){
            printf("%d\n", i);
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,a,sum;
bitset<4000003>f;
int main(){
	f[0]=1;
	scanf("%d",&n);
	while (n--){
		scanf("%d",&a);
		f|=f<<a,sum+=a;
	}
	for (register int i=(sum+1)/2;i<=sum;i++)
	 if (f[i]) return printf("%d\n",i),0;
}

Measured memory_bytes: 1792
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.NoSuchElementException;

public class Main {
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		int N = sc.nextInt();
		int K = sc.nextInt();
		long ans = 0;
		if (K % 2 == 1) {
			ans = (long)Math.pow(N/K, 3);
		} else {
			int a = 0;
			if (N/(K/2) > 0) {
				a = 1;
			}
			ans = (long)Math.pow(N/K, 3) + (long)Math.pow((N-K/2)/K + a, 3);
		}
		System.out.println(ans);
	}
}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }

    private int readByte() {
        if (hasNextByte())
            return buffer[ptr++];
        else
            return -1;
    }

    private static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr]))
            ptr++;
        return hasNextByte();
    }

    public String next() {
        if (!hasNext())
            throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong() {
        if (!hasNext())
            throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
            throw new NumberFormatException();
        return (int) nl;
    }

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


Measured memory_bytes: 21204