akhauriyash/Code-Regression huggingface dataset:
import static java.lang.Integer.parseInt;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * A Thief (0-1 Knapsack problem)
 */
public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = "";

		int c = 0;
		while (!(line = br.readLine()).equals("0")) {
			c++;
			int w = parseInt(line);
			int n = parseInt(br.readLine());

			int[][] dp = new int[n + 1][w + 1];
			int[] vs = new int[n + 1];
			int[] ws = new int[n + 1];

			for (int i = 1; i < n + 1; i++) {
				line = br.readLine();
				vs[i] = parseInt(line.substring(0, line.indexOf(',')));
				ws[i] = parseInt(line.substring(line.indexOf(',') + 1));
			}

			int maxv = 0;
			int minw = w;
			for (int i = 1; i < n + 1; i++) {
				for (int j = 1; j < w + 1; j++) {
					if (j >= ws[i]) {
						dp[i][j] = Math.max(dp[i - 1][j - ws[i]] + vs[i],
								dp[i - 1][j]);
						//
						if (dp[i][j] > maxv) {
							maxv = dp[i][j];
							minw = j;
						} else if (dp[i][j] == maxv) {
							minw = j < minw ? j : minw;
						}
					} else {
						dp[i][j] = dp[i - 1][j];
					}
				}
			}
			System.out.print("Case " + c + ":\n" + maxv + "\n" + minw + "\n");
		}

	}

}

Measured memory_bytes: 26568
#include <iostream>
#include <iomanip>
#include <valarray>
#include <cmath>

using namespace std;

int main() {
    cout << setprecision(20) << fixed;

    long long int n;
    cin >> n;

    auto input = valarray<long long int>(n);
    for (long long int i = 0; i < n; ++i) {
        cin >> input[i];
    }
    cout << input.min() << " " << input.max() << " " << input.sum() << "\n";
    return 0;
}


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

int main() {
  int count = 0; 
  string s;
  cin >> s;
  
  for (int i = 0; i < 3; i++) {
    if (s.at(i) == '1') {
      count += 1;
    }
  }
  cout << count << endl;
}

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

int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    int ans = 0;
    int left = 0, right = n-1;
    while(left < right){
        while(left < n && s[left] == 'R') left++;
        while(right >= 0 &&s[right] == 'W') right--;
        if(left < right && left < n && s[left] == 'W' && right >= 0 &&s[right] == 'R'){
            ans++;
            left++;
            right--;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3756
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 4e5 + 5;
const ll LINF = 1e18 + 5;
int n, a[N], b[N], c[N], d[N];
int nxt[N]; 
bool match[N];
void kmp_pre(int s[], int m, int nxt[])
{
	int i = 0, j = nxt[0] = -1;
	while(i<m)
	{
		while(j!=-1&&s[i]!=s[j]) j = nxt[j];
		nxt[++i] = ++j;
	}
}
void kmp_work(int s[], int n, int t[], int m) 
{
	int i = 0, j = 0;
	kmp_pre(s, n, nxt);
	while(i<m)
	{
		while(j!=-1&&t[i]!=s[j]) j = nxt[j];
		i++; j++;
		if(j>=n)
		{
			match[i-n] = 1;
			j = nxt[j];
		}
	}
}
int main()
{
 	ios::sync_with_stdio(false);
 	cin.tie(0);
 	cin >> n;
 	for(int i=0; i<n; i++)
 	{
 		cin >> a[i];
 		a[n+i] = a[i];
 		c[i] = c[n+i] = a[i];
 	}
 	for(int i=0; i<n; i++) 
	{
		cin >> b[i];
		d[i] = d[n+i] = b[i];
	}
 	for(int i=2*n-1; i>=1; i--) a[i] ^= a[i-1];
 	for(int i=n-1; i>=1; i--) b[i] ^= b[i-1];
 	kmp_work(b+1, n-1, a+1, 2*n-1);
 	vector <pii> ans;
 	for(int i=0; i<n; i++)
 	{
 		if(match[i])
 		{
 			ans.emplace_back(i, c[i]^d[0]);
 		}
 	}
 	for(auto it : ans) cout << it.first << ' ' << it.second << '\n';
	return 0;
}


Measured memory_bytes: 12400
#define _USE_MATH_DEFINES
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <math.h>
#include <complex>
#include <cassert>
#define rep(i,a,b) for (int i = (a); i < (b); i++)
#define case(i) cout<<"Case #"<<i<<": "
using namespace std;
typedef long long int ll;
typedef complex<double> com;
const int mod = 1e9 + 7;
const int MOD = 998244353;
const ll INF = 4e18;



int main(){
	string s, t; cin >> s >> t;
	vector<string> ans;
	rep(i, t.size() - 1, s.size()) {
		int cnt = 0; string u = s.substr(i-t.size()+1,t.size());
		rep(j, 0, t.size()) {
			if (u[j] == '?' || u[j] == t[j]) cnt++;
		}
		if (cnt == t.size()) {
			string sub = s;
			rep(j, 0, u.size()) sub[j + i - t.size() + 1] = t[j];
			rep(j, 0, s.size()) if (sub[j] == '?') sub[j] = 'a';
			ans.push_back(sub);
		}
	}
	if (ans.size() == 0) {
		cout << "UNRESTORABLE" << endl;
		return 0;
	}
	sort(ans.begin(), ans.end());
	cout << ans[0] << endl;
	return 0;
}

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

long long n,w,we[100004],v[100004],dp[100004];

int main() {
    scanf("%lld%lld",&n,&w);
    for(int i=0;i<n;++i)    scanf("%lld%lld",we+i,v+i);
    memset(dp,0,sizeof(dp));
    for(int i=0;i<n;++i)
        for(int j=w;j>=we[i];--j)
            dp[j] = max(dp[j-we[i]]+v[i],dp[j]);

    printf("%lld",dp[w]);
    return 0;
}

//long long n,w,we[100004],v[100004],dp[102][100004];
//
//int main() {
//    scanf("%lld%lld",&n,&w);
//    for(int i=0;i<n;++i)    scanf("%lld%lld",we+i,v+i);
//    memset(dp,0,sizeof(dp));
//    for(int i=0;i<n;++i)
//        for(int j=0;j<=w;++j) {
//            dp[i+1][j] = max(dp[i][j],dp[i+1][j]);//atleast equivalent to old items profit
//            if(j+we[i]>w) {
//                dp[i+1][w] = max(dp[i+1][w],dp[i][j]);
//                continue;
//            }
//            dp[i+1][j+we[i]] = max(dp[i+1][j+we[i]],dp[i][j] + v[i]);
//        }
//
////    for(int i=0;i<=n;++i) {
////        for(int j=0;j<=w;++j)
////            printf("%lld ",dp[i][j]);
////        cout<<endl;
////    }
//    printf("%lld",dp[n][w]);
//    return 0;
//}



Measured memory_bytes: 1024
#include<stdio.h>
 
int x,a,i;
 
int main(){
    scanf("%d",&x);
    while(x!=0){
        for(i=0;i<9;i++){
            scanf("%d",&a);
            x=x-a;
        }
        printf("%d\n",x);
        scanf("%d",&x);
    }
    return 0;
}

Measured memory_bytes: 1028
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main(void){
    int n;
    cin >> n;
    vector<pair<int,int>> a,b;
    bool flag[n];
    int w,h;
    rep(i,n){
        flag[i] = true;
        scanf("%d %d", &w,&h);
        a.emplace_back(w,h);
    }
    rep(i,n){
        scanf("%d %d", &w,&h);
        b.emplace_back(w,h);
    }
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    int ans = 0;
    rep(i,n){
        int max = -1;
        int max2 = INT_MAX;
        rep(j,n){
            if(a[j].first>=b[i].first)break;
            if(a[j].second<b[i].second&&flag[j]&&a[j].second > max){
                max = a[j].second;
                max2 = j;
            }
        }
        if(max2 != INT_MAX){
            flag[max2] = false;
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

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

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int N,M;
int k[20];
int s[20][20];
int p[20];
int ans;
int state[10];



bool check(){
    /**
    for(int i = 0; i < N; i++){
        cout << state[i];
    }
    cout << "\n";
    **/
    
    for(int i = 0; i < M; i++){
        ll num = 0;
        for(int j = 0; j < N; j++){
            num += s[i][j]*state[j];
        }
        if(num%2 != p[i]){
            //cout << i << "  " << num << "\n";
            return false;
        }
    }
    return true;
}

void dfs(int depth){
    if(depth >= N){
        if(check()) ans++;
        return ;
    }
    else{
        state[depth] = 1;
        dfs(depth+1);
        state[depth] = 0;
        dfs(depth+1);
    }
}

int main(){
    ans = 0;
    Fill(s, 0);
    cin >> N >> M;
    ll S;
    
    
    for(ll i = 0; i < N; i++){
        cin >> k[i];
        for(ll j = 0; j < k[i]; j++){
            cin >> S;
            s[i][S-1] = 1;
        }
    }
    for(ll i = 0; i < M; i++){
        cin >> p[i];
    }
    
    dfs(0);
    cout << ans << "\n";
    
    return 0;
} 

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <set>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <iomanip>
#include <map>
#include <utility>
#include <numeric>
#include <chrono>
#include <ctime>
#include <bitset>
#include <iterator>
#include <cmath>
#include <stack>
#include <random>

#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define debug(x) cerr << #x << ": " << x << ", "
#define debugln(x) cerr << #x << ": " << x << '\n'

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

using namespace std;
using ll = long long;
using P = pair<ll, ll>;

constexpr ll mod = 1e9+7;
const double PI = acos(-1.0);
mt19937_64 engine(chrono::steady_clock::now().time_since_epoch().count());

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

  int n; cin >> n;
  vector<int> length(3); cin >> length[0] >> length[1] >> length[2];
  vector<int> L(n);
  rep(i, n) cin >> L[i];

  int base = 1;
  rep(i, n) {
    base *= 3;
  }
  int ans = INT_MAX;
  vector<int> vec[3];
  vector<int> dp[2005];
  for(int i=0; i<base; i++) {
    int tmp = i;
    rep(j, 3) {
      vec[j].clear();
    }
    for(int j=0; j<n; j++) {
      int rem = tmp%3;
      vec[rem].push_back(L[j]);
      tmp /= 3;
    }
    if (vec[0].size() * vec[1].size() * vec[2].size() == 0) continue;
    int now = 0;
    for(int j=0; j<3; j++) {
      map<int, int> mp;
      map<int, int> mp2;
      for(int p=0; p<vec[j].size(); p++) {
        mp[0] = 0;
        for(auto e: mp) {
          if (mp2[e.first+vec[j][p]] == 0) {
            mp2[e.first+vec[j][p]] = e.second+10;
          } else {
            mp2[e.first+vec[j][p]] = min(mp2[e.first+vec[j][p]], e.second+10); 
          }
        }
        for(auto e: mp) {
          if (mp2[e.first] == 0) {
            mp2[e.first] = e.second;
          } else {
            mp2[e.first] = min(mp2[e.first], e.second);
          }
        }
        mp = mp2;
        mp2.clear();
      }
      int tmp = INT_MAX;
      for(auto e: mp) {
        //debugln("piyo");
        if (e.first == 0) continue;
        //debug(i);debug(j);debug(e.first);debugln(e.second);
        chmin(tmp, e.second+abs(e.first-length[j]));
      }
      now += tmp;
    }
    chmin(ans, now);
  }
  cout << ans-30 << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long 
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pii pair<int,int>
using namespace std;

int main(){
    fast 
    int n,k;
    cin>>n>>k;
    vector<int>a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    sort(a.begin(),a.end());
    ll ans=0;
    for(int i=0;i<k;i++)ans+=a[i];
    cout<<ans;
    return 0;
}

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

int main(){
  int a, b;
  cin >> a >> b;
  string s;
  cin >> s;
  string ans = "Yes";
  for(int i = 0; i < s.size(); i++){
    if(i == a){
      if(s[i] != '-') ans = "No";
    }else if(i != a){
      if(s[i] == '-') ans = "No";
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
/* #define	rep(i, n) for (int i = 0; i < (n); ++i) */
using	namespace std;
/* using	ll = long long; */
/* using	P = pair<int, int>; */

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

	int			n;
	/* int			max; */
	/* int			second_max; */
	cin >> n;
	vector<int>	A(n);
	vector<int>	B;

	/* rep(i, n) */
	/* 	cin >> A.at(i); */
	for (int &a : A)
		cin >> a;
	B = A;
	sort(B.rbegin(), B.rend());
	/* max = B.at(0); */
	/* second_max = B.at(1); */
	for (int a : A)
	/* { */
		cout << (a != B.at(0) ? B.at(0) : B.at(1)) << endl;
		/* if (a != B.at(0)) */
		/* 	cout << B.at(0) << endl; */
		/* else */
		/* 	cout << B.at(1) << endl; */
	/* } */
}


Measured memory_bytes: 3200
# coding: utf-8
# Your code here!


n = int(input())

p = [int(i) for i in input().split()]


ans = 0
for i in range(n-2):
    if p[i] < p[i+1] < p[i+2] or p[i] > p[i+1] > p[i+2]:
        ans += 1

print(ans)
    












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

using namespace std;

const int INF = 2e9, N = 1e5 + 15;

int n, a[ N ], h[ N ], dp[ N ];

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

    cin >> n;
    for(int i = 1; i <= n; i += 1) {
        cin >> h[ i ];
    }
    dp[ 0 ] = dp[ 1 ] = 0;
    for(int i = 2; i <= n; i += 1) {
        int x = INF, y = INF;
        x = dp[ i - 1 ] + abs(h[ i ] - h[ i - 1 ]);
        if( i > 2 ) y = dp[ i - 2 ] + abs(h[ i ] - h[ i - 2 ]);
        dp[ i ] = min(x, y);
    }
    cout << dp[ n ] << '\n';
    return 0;
}


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

int main() {
  int N,i,sum,M;
  cin>>N;
  M=N;
  for(i=0;i<9;i++){
  	sum+=M%10;
    M/=10;
  }
  if(N%sum==0){
  	cout<<"Yes"<<endl;
  }else{
  	cout<<"No"<<endl;
  }
}



Measured memory_bytes: 256
/*
    Author : DemonStar
*/

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
#define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) x.begin(), x.end()
#define loop(i, n) for(ll i = 0; i < n; i++)
#define pl pair<ll, ll>
#define vl vector<ll>
#define endl '\n'
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}

#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};


template <typename T, typename TT>
ostream &operator<<(ostream &os, const pair<T, TT> &t) {
    return os << t.first << " " << t.second;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &t) {
    for (auto &i : t) os << i << " ";
    return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
    for (T &t : v) is >> t;
    return is;
}
template <typename T1, typename T2>
istream &operator>>(istream &is, vector<pair<T1, T2>> &v) {
    for (pair<T1, T2> &t : v) is >> t.first >> t.second;
    return is;
}

const ll mod = 1e9 + 7;

int main()
{

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    ll n;
    cin >> n;
    string s;
    cin >> s;
    if (s.size() > n)
        cout << s.substr(0, n) + "..." << endl;
    else
        cout << s << endl;

#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s";
#endif

    return 0;
}

Measured memory_bytes: 3604
from typing import List, Tuple


def main():
    n, m = map(int, input().split())
    g = []
    for _ in range(m):
        a, b = map(int, input().split())
        g.append((a, b))
    print(osp(n, g))


def osp(n: int, g: List[Tuple[int, int]]) -> int:
    v = [False] * n
    g = set(g)

    return dfs(0, v, n, g)


def dfs(i, v, n, g):
    v[i] = True
    if all(v):
        v[i] = False
        return 1

    cnt = 0
    for j in range(n):
        if v[j]:
            continue
        if not ((i + 1, j + 1) in g or (j + 1, i + 1) in g):
            continue
        cnt += dfs(j, v, n, g)

    v[i] = False
    return cnt


if __name__ == '__main__':
    main()


Measured memory_bytes: 10252
#include <bits/stdc++.h>
using namespace std;
// stock = A; loop { buy B; if stock <= C then add D }
int solve(long long A, long long B, long long C, long long D)
{
    if (D < B) return 0;
    if (A < B) return 0;
    if (C >= B) return 1;
    A %= B;
    D %= B;
    if (A > C) return 0;
    if (D == 0) return 1;
    long long E = __gcd(B, D);
    // C < A + kE < B となる k が存在すれば終了する
    long long k = (C - A) / E + 1;
    return A + k * E >= B;
}
int main()
{
    int T; cin >> T;
    for (int i = 0; i < T; i++) {
        long long A, B, C, D;
        cin >> A >> B >> C >> D;
        int ans = solve(A, B, C, D);
        cout << (ans == 1 ? "Yes" : ans == 0 ? "No" : to_string(ans)) << '\n';
    }
    return 0;
}

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


int main() {
	int n, v[50], c[50];
	cin >> n;

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

	int sum = 0;
	for (int i = 0; i < n; i++) {
		if (v[i] > c[i]) sum += v[i] - c[i];
	}

	cout << sum << endl;



	//system("pause");
	return 0;
}

Measured memory_bytes: 256
//Illumination
#include <iostream>
#include <queue>

using namespace std;
static const int MAX = 100;
static const int dx1[6] = {1, 1, 0, -1, 0, 1};
static const int dy1[6] = {0, 1, 1, 0, -1, -1};
static const int dx2[6] = {1, 0, -1, -1, -1, 0};
static const int dy2[6] = {0, 1, 1, 0, -1, -1};

int W, H;
bool A[MAX][MAX], B[MAX][MAX], visited[MAX][MAX];

void bfs(int x, int y) {
    if(A[y][x]) return;
    if(visited[y][x]) return;
    queue<pair<int, int> > Q;
    Q.push(make_pair(x, y));
    visited[y][x] = true;
    while(!Q.empty()) {
        pair<int, int> p = Q.front();
        Q.pop();
        B[p.second][p.first] = false;
        for(int i = 0; i < 6; i++) {
            int sx, sy;
            if(p.second % 2 == 0) {
                sx = p.first + dx1[i];
                sy = p.second + dy1[i];
            } else {
                sx = p.first + dx2[i];
                sy = p.second + dy2[i];
            }
            if(sx < 0 || sy < 0 || sx >= W || sy >= H) continue;
            if(A[sy][sx]) continue;
            if(visited[sy][sx]) continue;
            Q.push(make_pair(sx, sy));
            visited[sy][sx] = true;
        }
    }
}

int main() {
    cin >> W >> H;
    for(int i = 0; i < H; i++) for(int j = 0; j < W; j++)
            cin >> A[i][j];
    for(int i = 0; i < H; i++) for(int j = 0; j < W; j++)
            B[i][j] = true;
    for(int i = 0; i < H; i++) for(int j = 0; j < W; j++)
            visited[i][j] = false;

    for(int i = 0; i < H; i++) {
        bfs(0, i);
        bfs(W - 1, i);
    }
    for(int j = 0; j < W; j++) {
        bfs(j, 0);
        bfs(j, H - 1);
    }

    int cnt = 0;

    for(int i = 0; i < H; i++) {
        for(int j = 0; j < W; j++) {
            if(!B[i][j]) continue;
            for(int k = 0; k < 6; k++) {
                int sx, sy;
                if(i % 2 == 0) {
                    sx = j + dx1[k];
                    sy = i + dy1[k];
                } else {
                    sx = j + dx2[k];
                    sy = i + dy2[k];
                }
                if(sx < 0 || sy < 0 || sx >= W || sy >= H) {cnt++; continue;}
                if(!B[sy][sx]) cnt++;
            }
        }
    }

    cout << cnt << endl;

    return 0;
}


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

int main() {
	int n;
	cin >> n;
	long long ans = 0;
	rep(i, n) {
		int l, r;
		cin >> l >> r;
		ans += r - l + 1;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<string>

using namespace std;
int main(){
    string s,p;
    cin >> s >> p;
    s = s + s;
    if(s.find(p) != -1){
        printf("Yes\n");
    } else{
        printf("No\n");
    }
    
    
}


Measured memory_bytes: 3192
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <numeric>

template <class T, class U>
inline bool chmin(T &lhs, const U &rhs) {
  if (lhs > rhs) {
    lhs = rhs;
    return true;
  }
  return false;
}

template <class T, class U>
inline bool chmax(T &lhs, const U &rhs) {
  if (lhs < rhs) {
    lhs = rhs;
    return true;
  }
  return false;
}

// [l, r) from l to r
struct range {
  struct itr {
    int i;
    constexpr itr(int i_): i(i_) { }
    constexpr void operator ++ () { ++i; }
    constexpr int operator * () const { return i; }
    constexpr bool operator != (itr x) const { return i != x.i; }
  };
  const itr l, r;
  constexpr range(int l_, int r_): l(l_), r(std::max(l_, r_)) { }
  constexpr itr begin() const { return l; }
  constexpr itr end() const { return r; }
};

// [l, r) from r to l
struct revrange {
  struct itr {
    int i;
    constexpr itr(int i_): i(i_) { }
    constexpr void operator ++ () { --i; }
    constexpr int operator * () const { return i; }
    constexpr bool operator != (itr x) const { return i != x.i; }
  };
  const itr l, r;
  constexpr revrange(int l_, int r_): l(l_ - 1), r(std::max(l_, r_) - 1) { }
  constexpr itr begin() const { return r; }
  constexpr itr end() const { return l; }
};

int main() {
  int N, K;
  std::cin >> N >> K;
  std::vector<bool> A(N);
  for (int i: range(0, K)) {
    int d;
    std::cin >> d;
    for (int j: range(0, d)) {
      int a;
      std::cin >> a;
      --a;
      A[a] = true;
    }
  }
  std::cout << std::count(A.begin(), A.end(), false) << '\n';
  return 0;
}


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

int dp[100005][3];

int main() {
	int n;
	cin>>n;
	int ar[n][3];
	for(int i=0;i<n;i++)
		if(i) cin>>ar[i][0]>>ar[i][1]>>ar[i][2];
		else cin>>dp[i][0]>>dp[i][1]>>dp[i][2];
	for(int i=1;i<n;i++)
		for(int j=0;j<3;j++)
			for(int k=0;k<3;k++)
				if(k!=j)
					dp[i][j]=max(dp[i][j],dp[i-1][k]+ar[i][j]);
	cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]))<<'\n';
}

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

class Program
{
    static void Main(string[] args)
    {
        var n = long.Parse(Console.ReadLine());

        var a = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();

        long ans = 1;

        if(a.Any(t => t == 0))
        {
            Console.WriteLine("0");
            return;
        }

        if(a.Any(t => t > 1000000000000000000))
        {
            Console.WriteLine("-1");
            return;
        }

        // 桁数を毎回調べる
        for (int i = 0; i < n; i++)
        {
            if(1000000000000000000d / a[i] < (double)ans)
            {
                Console.WriteLine("-1");
                return;
            }

            ans *= a[i];

            if (ans > 1000000000000000000 || ans <= 0)
            {
                ans = -1;
                break;
            }
        }

        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 41616
#include <iostream>
#include <set>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
#include <map>
#include <utility>
#include <list>
#include <climits>
#include <bitset>
#include <numeric>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repi(i, n) for(auto i = (n).begin(); i != (n).end(); i++)
#define in_arr(type, a, n) copy_n(istream_iterator<type>(cin), n, (a).begin());
#define ll long long int

int main(){
    int a, b;
    cin >> a >> b;
    if(a % 2 == 1 && b % 2 == 1){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
//大文字->小文字 tolower(),逆はtoupper()
//int a = stoi(c); 文字列をintへ
//途中の出力をそのまま残さない
//数値計算 個数以外はdouble
//map<キー,値> p は辞書。p[キー] = 値
//map 全探索
//auto begin = p.begin(), end = p.end();
//for (auto it = begin; it != end; it++) {}
//mapのキー：it->first mapのバリュー：it->second
//絶対値 abs()
//入力は空白で切れる
//大文字判定 isupper(文字) 小文字判定 islower(文字)
//do{}while(next_permutation(ALL(配列)))
//while(N)で回すとき、Nはコピーを作っておく
#include <bits/stdc++.h>
#define rep(i,N) for(int i = 0; i < N;i++)
#define ALL(a) (a).begin(),(a).end()
#define ll long long int
using namespace std;

// K進数でのNの桁数
ll dig(ll N, ll K) {
	ll dig = 0;
	while (N) {
		dig++;
		N /= K;
	}
	return dig;
}
// x,yの最大公約数
ll gcd(ll x, ll y) {
	ll r;
	while (x%y) {
		r = x % y;
		x = y;
		y = r;
	}
	return y;
}

//nC2の計算
ll C(ll N) {
	return N * (N - 1) / 2;
}

int main() {
	ll X; cin >> X;

	ll ans = 0;
	ans += (X / 500) * 1000;
	X = (X % 500);
	ans += (X/5)*5;

	cout << ans << endl;
}

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

int cou[100001];

int main()
{
	int i = 1, j = 0, n, a[100001], ans = 0;
	
	cin >> n;

	while(i <= n - j)
	{
		cin >> a[i];

		if (a[i] >= 100001)
		{
			ans += 1;
			j++;
		}
		else
		{
			cou[a[i]]++;
			i++;
		}
	}

	sort(a + 1, a + n + 1 - j);

	for (int i = 1; i <= 100000; i++)
	{
		if (cou[i] < i)
		{
			ans += cou[i];
		}
		else if (cou[i] > i)
		{
			ans += cou[i] - i;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 640
program main
implicit none
character :: s*100000
integer   :: i, l, res, iloop, chk( 2 )

read(*,*) s
l = len_trim( s )

do iloop = 1, 2

if( iloop == 1 ) then
   res = 0
else
   res = 1
   if( s(1:1) == '0' ) then
      s(1:1) = '1'
   else
      s(1:1) = '0'
   end if
end if
do i = 2, l
   if( s(i:i) /= s(i-1:i-1) ) then
   else if( i == 2 ) then
      if( s(i-1:i-1) =='0')then
         s(i:i) = '1'
      else
         s(i:i) = '0'
      end if
      res = res + 1
   else
      s(i:i) = s(i-2:i-2)
      res = res + 1
   end if
end do
chk( iloop ) = res
end do

write(*,'(i0)') minval( chk )

end program main


Measured memory_bytes: 700
local read = setmetatable({}, {__index = function(t, k) local a = {} for i=1,#k do table.insert(a, '*'..string.sub(k, i, i)) end local r = io.read local u = table.unpack or unpack return function() return r(u(a)) end end})
read.N = function(N) local t={} for i=1,N do t[i]=read.n() end return t end
string.totable = function(s) local t={} local u=string.sub for i=1,#s do t[i] = u(s, i, i) end return t end
string.split = function(s) local t={} for w in string.gmatch(s, "[^%s]+") do table.insert(t, w) end return (table.unpack or unpack)(t) end
----
local function array(n, default_val)
    local metatables = {}
    if default_val ~= nil then
        metatables[1] = {__index = function() return default_val end}
    end
    for i=2,n do
        metatables[i] = {__index = function(parent, k)
            local child = setmetatable({}, metatables[i-1])
            rawset(parent, k, child)
            return child
        end}
    end
    return setmetatable({}, metatables[n])
end
----
local N = read.n()
local A, B, C = {}, {}, {}
for i=1,N do
    A[i], B[i], C[i] = read.nnn()
end
local tbl = array(2, 0)
local a, b, c = 1, 2, 3
tbl[1][a] = A[1]
tbl[1][b] = B[1]
tbl[1][c] = C[1]
for i=1,N-1 do
    tbl[i+1][a] = math.max(tbl[i][b]+A[i+1], tbl[i][c]+A[i+1])
    tbl[i+1][b] = math.max(tbl[i][a]+B[i+1], tbl[i][c]+B[i+1])
    tbl[i+1][c] = math.max(tbl[i][a]+C[i+1], tbl[i][b]+C[i+1])
end
print(math.max(tbl[N][a], tbl[N][b], tbl[N][c]))

Measured memory_bytes: 28792
#include <iostream>
#include <cmath>
#include <climits>
#include <string>
#include <numeric>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <functional>
#include <iomanip>

using namespace std;
using ll = long long;

template<typename T> void print(T t) { cout << t << endl; }

bool check(int a, int s, int c) {
	for (int ss = 1; ss < s; ss++) a /= 10;
	return a % 10 == c;
}
int main() {
	ll N, A, B;
	cin >> N >> A >> B;

	if (N == 1) {
		if (A == B) {
			print(1);
		}
		else {
			print(0);
		}
	}
	else {
		if (A > B) {
			print(0);
		}
		else {
			ll maxSum = A + (N - 1) * B;
			ll minSum = B + (N - 1) * A;
			print(maxSum - minSum + 1);
		}
	}
}



Measured memory_bytes: 3628
#include <iostream>
#include <cstring>

using namespace std;

char dx[] = {-1,1,0,0};
char dy[] = {0,0,-1,1};
char dice[6][2] = {
	{4,2}, {3,5}, {5,0}, {1,4}, {0,3}, {2,1}
};

int board[9], goal[9];

void dfs(int x, int y, int px, int py, int step, int &res){
	if(step >= res) return;
	int space = 3*x+y;
	for(int i=0;i<4;i++){
		int nx = x + dx[i], ny = y + dy[i];
		if(nx<0||3<=nx||ny<0||3<=ny) continue;
		if(nx==px&&ny==py) continue;
		int mv = 3*nx+ny;
		int tmp = board[mv];
		board[space] = dice[board[mv]][i/2];
		board[mv] = 6;
		int dif = 0;
		for(int j=0;j<9;j++) dif += (goal[j]!=board[j]/2);
		if(dif==0) res = step;
		if(step+dif-1<res) dfs(nx, ny, x, y, step+1, res);
		board[space] = 6;
		board[mv] = tmp;
	}
}

int main(){
	int x, y;
	while(cin >> y >> x, y){
		char c;
		for(int i=0;i<9;i++) {
			cin >> c;
			if(c=='W') goal[i] = 0;
			if(c=='B') goal[i] = 1;
			if(c=='R') goal[i] = 2;
			if(c=='E') goal[i] = 3;
		}
		memset(board,0,sizeof(board));
		board[3*(x-1)+y-1] = 6;
		int dif = 0;
		for(int i=0;i<9;i++) dif += (goal[i]!=board[i]/2);
		int res = dif ? 31 : 0;
		dfs(x-1,y-1,-1,-1,1,res);
		cout << (res==31?-1:res) << endl;
	}
}

Measured memory_bytes: 868
#include<stdio.h>
#include<stdlib.h>
struct node{
  int key;
  struct node *parent;
  struct node *right;
  struct node *left;
};
typedef struct node *Node;
Node T;
#define NIL NULL;
void Insert(int);
Node Find(int);
Node Successor(Node);
Node Minimun(Node);
void Delete(int);
void Preorder(Node);
void Inorder(Node);
int main()
{
  int n,i,key;
  char S[7];
  
  scanf("%d",&n);

  for(i=0;i<n;i++){
    scanf("%s",S);
    if(S[0]=='i'){
      scanf("%d",&key);
      Insert(key);
    }
    else if(S[0]=='f'){
      scanf("%d",&key);
      if(Find(key)!=NULL)printf("yes\n");
      else printf("no\n");
    }
    else if(S[0]=='d'){
      scanf("%d",&key);
      Delete(key);
    }
    else{
      Inorder(T);
      printf("\n");
      Preorder(T);
      printf("\n");

    }
  }
  return 0;
}

void Insert(int key)
{
  Node y,x,z;
  y=NIL;
  x=T;
  z=malloc(sizeof(struct node));
  z->key=key;
  z->left=NIL;
  z->right=NIL;
  while(x!=NULL){
    y=x;
    if( z->key < x->key )x=x->left;
    else x=x->right;
  }
  z->parent=y;
  if(y==NULL){
    T=z;
  }
 else if(z->key<y->key){
      y->left=z;
  }
  else{
    y->right=z;
  }
}

Node Find(int key)
{
  Node TT;
  TT=T;
  while(TT!=NULL && TT->key!=key){
    if(key<TT->key)TT=TT->left;
    else TT=TT->right;
  }
  if(TT==NULL)return NULL;
  else return TT;
}

Node Minimum(Node TT)
{
  while(TT->left!=NULL){
    TT=TT->left;
  }
  return TT;
}

Node Successor(Node Z)
{
  Node X;
  if(Z->right!=NULL)return Minimum(Z->right);
  X=Z->parent;
  while(X!=NULL && Z==X->right){
    Z=X;
    X=X->parent;
  }
  return X;
}

void Delete(int key)
{
  Node X,Y,Z=Find(key);  

  if(Z->left==NULL||Z->right==NULL)Y=Z;
  else{
     Y=Successor(Z);
  } 
  if(Y->left!=NULL)X=Y->left;
  else{
     X=Y->right;
  }
  
  if(X!=NULL)X->parent=Y->parent;
  if(Y->parent==NULL)T=X;
  else if(Y==Y->parent->left)Y->parent->left=X;
  else Y->parent->right=X;
 
  if(Y!=Z)Z->key=Y->key;
}


void Preorder(Node T)
{
  printf(" %d",T->key);
  if(T->left!=NULL){
    Preorder(T->left);
  }
  if(T->right!=NULL){
    Preorder(T->right);
  }

}

void Inorder(Node T)
{
  if(T->left!=NULL && T->right!=NULL){
    Inorder(T->left);
    printf(" %d",T->key);
    Inorder(T->right);

  }
  if(T->left!=NULL && T->right==NULL){
   Inorder(T->left);
     printf(" %d",T->key);
  }

  if(T->right!=NULL && T->left==NULL){
  printf(" %d",T->key);
 Inorder(T->right);

  }
  if(T->left==NULL && T->right==NULL)printf(" %d",T->key);

}



Measured memory_bytes: 20468
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
using namespace std;
int n,x,y;
int cnt[2007];
int len(int u,int v){
	int res;
	if (v<=x) return v-u;
	if (u>=y) return v-u;
	if (u<=x && v>=y) return x-u+v-y+1;
	if (x<=u && v<=y) res=min(v-u,y-v+u-x+1);
	else if (x<=u && u<=y) res=min(v-u,v-y+1+u-x);
	else  res=min(v-u,x-u+1+y-v);
	return res;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>x>>y;
	for (int i=1; i<n; i++)
		 for (int j=i+1; j<=n; j++)
			 ++cnt[len(i,j)];
	for (int i=1; i<n; i++) cout<<cnt[i]<<endl;
	return 0;
}

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



int main(){
    int a,b,c,x,y;
    int sum;
    
    cin>>a>>b>>c>>x>>y;

    if((2*c)>=(a+b)) sum=a*x+b*y;

    if(2*c<=a&&2*c<=b){
        if(x>y){
            sum=2*c*x;
        }
        else{
            sum=2*c*y;
        }
    }

   else if(2*c<=b){
        if(x>y){
            sum=2*c*y+a*(x-y);
        }
        else{
            sum=2*c*y;
        }
    }

   else if(2*c<=a){
          if(x>y){
            sum=2*c*x;
        }
        else{
            sum=2*c*x+b*(y-x);
        }
    }

    else if(2*c>a && 2*c>b && 2*c<(a+b)){
        if(x>y){
             sum=2*c*y+a*(x-y);
        }
        else{
            sum=2*c*x+b*(y-x);
        }
    }
   cout<<sum<<endl;
   
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ

		Scanner sc1 = new Scanner(System.in);

		int a = sc1.nextInt();
		int b = sc1.nextInt();
		int x = sc1.nextInt();

		boolean ans = false;

		if (x - a >= 0) {
			if (a + b -x >= 0) {
				ans = true;
			}
		}

		if (ans) {
			System.out.println("YES");
		}
		else {
			System.out.println("NO");
		}


		sc1.close();

	}

}


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


def solve(N: int, M: int, Q: int, L: "List[int]", R: "List[int]", p: "List[int]", q: "List[int]"):
    matrix = [[0]*(N+1) for _ in range(N+1)]

    for i in range(M):
        matrix[L[i]][R[i]] += 1
    
    for i in range(1,N+1):
        for j in range(1,N+1):
            matrix[i][j] += matrix[i-1][j]+matrix[i][j-1]-matrix[i-1][j-1]
    
    for i in range(Q):
        pp,qq = p[i],q[i]
        print(matrix[qq][qq]-matrix[pp-1][qq]-matrix[qq][pp-1]+matrix[pp-1][pp-1])

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]"
    R = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    p = [int()] * (Q)  # type: "List[int]"
    q = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        p[i] = int(next(tokens))
        q[i] = int(next(tokens))
    solve(N, M, Q, L, R, p, q)

if __name__ == '__main__':
    main()


Measured memory_bytes: 29100
from heapq import*
i=input
s=sorted
def f(x):
 s,n,*h=0,len(x)
 while n:
  while x and x[-1][0]>=n:k,l,r=x.pop();heappush(h,(r-l,l,r))
  if h:s+=heappop(h)[1]
  n-=1
 return s+sum(r for*_,r in x+h)
for _ in'_'*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:
  k,l,r=map(int,i().split())
  if l>r:x+=(k,l,r),
  else:y+=(n-k,r,l),
 print(f(s(x))+f(s(y)))

Measured memory_bytes: 49192
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::Read;
#[allow(dead_code)]
fn getline() -> String {
    let mut ret = String::new();
    std::io::stdin().read_line(&mut ret).ok().unwrap();
    ret
}
fn get_word() -> String {
    let mut stdin = std::io::stdin();
    let mut u8b: [u8; 1] = [0];
    loop {
        let mut buf: Vec<u8> = Vec::with_capacity(16);
        loop {
            let res = stdin.read(&mut u8b);
            if res.unwrap_or(0) == 0 || u8b[0] <= b' ' {
                break;
            } else {
                buf.push(u8b[0]);
            }
        }
        if buf.len() >= 1 {
            let ret = String::from_utf8(buf).unwrap();
            return ret;
        }
    }
}

#[allow(dead_code)]
fn get<T: std::str::FromStr>() -> T { get_word().parse().ok().unwrap() }

fn solve() {
    let s: Vec<char> = get_word().chars().collect();
    let w: usize = get();
    for i in 0 .. s.len() {
        if i % w == 0 {
            print!("{}", s[i]);
        }
    }
    println!();
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


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

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define sz(v) (int)v.size()

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, n) for (int i = 0; i < (n); i++)
#define dFOR(i, a, b) for (int i = (b)-1; i >= a; i--)
#define dF0R(i, n) for (int i = (n)-1; i >= 0; i--)

#define print(x) cout << x << '\n';
#define dbg(x) cerr << ">>> " << #x << " = " << x << "\n";
#define finish(x) return cout << x << '\n', 0;

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef pair<ld, ld> pd;
typedef complex<ld> cd;


int N;
int h[100001];
int dp[100001];

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

    FOR (i,1,N+1) cin >> h[i];
    dp[1] = 0;
    dp[2] = abs(h[2]-h[1]);
    FOR (i,3,N+1) {
        int one = abs(h[i] - h[i-1]) + dp[i-1];
        int two = abs(h[i] - h[i-2]) + dp[i-2];
        dp[i] = min(one,two);
    }
    finish(dp[N]);






    return 0;
}


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

int powmod(int a, int n, int mod) {
	if (n == 0) return 1;
	if (n % 2) return (a * powmod(a, n - 1, mod)) % mod;
	return powmod((a * a) % mod, n / 2, mod);
}

int mod = 1000000007;
int n;
int a[100000];
int inv[100001];
int fact[100001];

signed main() {
	int i;
	
	cin >> n;
	rep(i, n) cin >> a[i];
	rep(i, n) inv[i + 1] = (inv[i] + powmod(i + 1, mod - 2, mod)) % mod;
	fact[0] = 1;
	rep(i, n) fact[i + 1] = ((i + 1) * fact[i]) % mod;
	
	int ans = 0;
	rep(i, n) {
		ans += (inv[i+1] + inv[n-i] - inv[1]) * a[i];
		ans %= mod;
	}
	ans *= fact[n];
	ans %= mod;
	cout << ans << endl;
	return 0;
}

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

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

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

ll powmod(ll m, ll p) {
    if (p == 0) return 1;
    ll tmp = powmod(m, p / 2);
    if (p & 1) return (tmp * tmp % MOD) * m % MOD;
    else return tmp * tmp % MOD;
}

const ll MAX = 200000;

vector<long long> fac(MAX, 0), finv(MAX, 0), inv(MAX, 0);
void initCombTable() {
    fac.at(0) = 1; fac.at(1) = 1;
    finv.at(0) = 1; finv.at(1) = 1;
    inv.at(1) = 1;
    for (ll i = 2; i < MAX; i++) {
        fac.at(i) = fac.at(i-1) * i % MOD;
        inv.at(i) = MOD - inv.at(MOD%i) * (MOD / i) % MOD;
        finv.at(i) = finv.at(i-1) * inv.at(i) % MOD;
    }
}
long long nCk(long long n, long long k) {
    if (n < 0 || k < 0 || n < k) return 0;
    return fac.at(n) * (finv.at(k) * finv.at(n-k) % MOD) % MOD;
}


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    initCombTable();
    ll n, m, k; cin >> n >> m >> k;

    ll ans = 0;
    for (ll i = 0; i <= k; i++) {
        (ans += (nCk(n - 1, i) * m) % MOD * powmod(m - 1, n - i - 1) % MOD) %= MOD;
    }
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 7868
#include <assert.h>
#include <ctype.h>
#include <errno.h>
#include <float.h>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <limits>
#include <locale>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <wchar.h>
#include <wctype.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <limits>
#include <map>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <istream>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <vector>
#include <cwchar>
#include <cwctype>
#include <complex.h>
#include <fenv.h>
using namespace std;
int main()
{
//	ios_base::sync_with_stdio(false);
	int n;
	cin>>n;
	cout<<(n<1200?"ABC":"ARC");
	return 0;
}


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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, M, V, P;
  cin >> N >> M >> V >> P;
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  sort(A.begin(), A.end(), greater<int>());

  auto f = [&](int x) -> int64_t {
    int64_t res = 1LL * (P - 1) * M;
    for (int i = P - 1; i < N; i++) {
      res += min(M, A[x] + M - A[i]);
    }
    return res;
  };

  int lo = P - 1, hi = N - 1;
  while (lo < hi) {
    int mi = (lo + hi + 1) / 2;
    if (A[P - 1] - A[mi] <= M && f(mi) >= 1LL * M * V) {
      lo = mi;
    } else {
      hi = mi - 1;
    }
  }
  cout << lo + 1 << '\n';
  return 0;
}


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

typedef long long ll;
typedef long double Double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

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

long long f(const long long n)
{
  // Modulus operator are expensive on most of the
  // computers. n & 3 will be equivalent to n % 4.

  switch(n & 3) // n % 4
  {
    case 0: return n;     // if n is multiple of 4
    case 1: return 1;     // If n % 4 gives remainder 1
    case 2: return n + 1; // If n % 4 gives remainder 2
    case 3: return 0;     // If n % 4 gives remainder 3
  }
}
void solve(long long A, long long B) {
  cout << (f(B) ^ (A > 0 ? f(A-1) : 0)) << endl;
}

int main() {
  long long A;
  scanf("%lld", &A);
  long long B;
  scanf("%lld", &B);
  solve(A, B);
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <cassert>
#include <exception>
#include <numeric>
using namespace std;
typedef long long ll;
typedef string str;
typedef pair<ll, ll> P;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<char> vc;
typedef vector<str> vs;
typedef vector<P> vp;
typedef vector<bool> vb;
#define rep(i, a, n) for (ll i = (a); i < (n); ++i)
#define rrep(i, a, n) for (ll i = (a); i > (n); --i)
#define erep(i, a, n) for (ll i = (a); i <= (n); ++i)
#define rerep(i, a, n) for (ll i = (a); i >= (n); --i)
#define all(c) (c).begin(), (c).end()
#define pb push_back
#define mp make_pair
#define sz(x) ((int)x.size())
#define print(X) cout << (X) << "\n"
#define _ << " " <<
static const int INF = 1e+9+7;


int main(){

  ll n,k;
  cin >> n >> k;
  k--;

  vll x(n);
  ll ans = INF;
  rep(i,0,n) {
    cin >> x[i];

    if(i >= k) {
      // 両方とも正or負になるとき
      if(x[i] * x[i-k] >= 0) {
        ans = min(ans, max(abs(x[i]), abs(x[i-k])));
      // 正負が逆側にあるとき
      } else {
        ans = min(ans, abs(x[i]) + abs(x[i-k]) + min(abs(x[i]), abs(x[i-k])));
      }
    }
  }

  print(ans);

  return 0;
}



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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define each(it,n) for(__typeof((n).begin()) it=(n).begin();it!=(n).end();++it)

using namespace std;

//////////////////////////////////////////////////

class UnionFind
{
public:
    vector<int> data;
    UnionFind(int size) : data(size, -1) {};

    bool unionSet(int x, int y) {
        x = root(x); y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y]; data[y] = x;
        }
        return x != y;
    }

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

    int root(int x) {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }

    int size(int x) {
        return -data[root(x)];
    }
};

//////////////////////////////////////////////////
int main() {
    int n, q;
    cin >> n >> q;
    UnionFind uf(n);
    rep(i, q) {
        int c, x, y;
        cin >> c >> x >> y;
        if (c == 0) {
            uf.unionSet(x, y);
        } else {
            cout << uf.find(x, y) << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 1236
n = int(input())
sa = input().split()

a = [0 for i in range(n)]
sumeven = 0
sumodd = 0
for i,sai in enumerate(sa):
    a[i] = int(sai)

    if i % 2 == 0:
        sumeven += a[i]
    else:
        sumodd += a[i]

ret = 0
sm = 0
for i,ai in enumerate(a):
    if i % 2 == 1:
        ret += max(-sm+1-ai,0)
        sm += max(ai, -sm+1)
    else:
        ret += max(sm+1 + ai, 0)
        sm += min(ai, -(sm+1))
ret2 = 0
sm = 0
for i,ai in enumerate(a):
    if i % 2 == 0:
        ret2 += max(-sm+1-ai,0)
        sm += max(ai, -sm+1)
    else:
        ret2 += max(sm+1 + ai, 0)
        sm += min(ai, -(sm+1))
        
print(min(ret,ret2))

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

void call(int n){
  int i = 1;
 CHECK_NUM:
  int x = i;
  if ( x % 3 == 0 ){
    cout << " " << i;
    goto END_CHECK_NUM;
  }
 INCLUDE3:
  if ( x % 10 == 3 ){
    cout << " " << i;
    goto END_CHECK_NUM;
  }
  x /= 10;
  if ( x ) goto INCLUDE3;
 END_CHECK_NUM:
  if ( ++i <= n ) goto CHECK_NUM;

  cout << endl;
}

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

    call(n);
}


Measured memory_bytes: 3084
#include <iostream>
using namespace std;
int main(){
    int N;
    cin>>N;
    int X[N+2];
    int skip0[N+1];
    int skip1[N];
    int sam=0;
    X[0] = 0;
    for(int i=1;i<=N;i++){
        cin>>X[i];
    }
    X[N+1] = 0;
    for(int i=0;i<=N;i++){
        skip0[i]=abs(X[i+1]-X[i]);
        if(i<=N)skip1[i] = abs(X[i+2]-X[i]);
        sam +=  skip0[i];
    }
    for(int i=0;i<N;i++){
        cout<<sam - skip0[i] - skip0[i+1] + skip1[i]<<endl;
    }
}


Measured memory_bytes: 2432