akhauriyash/Code-Regression huggingface dataset:
using System;

namespace _0044
{
    class Program
    {
        static void Main(string[] args)
        {
            bool[] prime = new bool[50050];
            for (int i = 0; i < 50050; i++)
            {
                prime[i] = true;
            }
            for (int i = 2; i <= 223; i++)
            {
                if (prime[i])
                {
                    for (int j = 2; i * j < 50050; j++)
                    {
                        prime[i * j] = false;
                    }
                }
            }
            while (true)
            {
                string x = Console.ReadLine();
                if (string.IsNullOrEmpty(x))
                {
                    break;
                }
                int a = int.Parse(x);
                int i;
                for (i = a - 1; !prime[i]; i--)
                {
                }
                Console.Write(i + " ");
                for (i = a + 1; !prime[i]; i++)
                {
                }
                Console.WriteLine(i);
            }
        }
    }
}

Measured memory_bytes: 9060
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<utility>
#include<functional>
#include<stack>
#include<queue>
#include<cmath>

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
# define MOD 1000000000+7
# define INF 1000000000
typedef long long ll;
using namespace std;
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }


int main() {
	string s;
	int cnt = 0;
	int ans = 0;
	cin >> s;

	rep(i, s.length()) {
		if (s[i] == 'A' || s[i] == 'T' || s[i] == 'C' || s[i] == 'G') {
		
			cnt++;
		}
		else {

			ans = max(ans, cnt);
			cnt = 0;
		}
	}
	ans = max(ans, cnt);
	if (cnt == s.length()) {
		cout << cnt << endl;
		return 0;
	}
	cout << ans << endl;
}



Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>

using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair
#define mt make_tuple

int main(void)
{
    cin.sync_with_stdio(false);
    int N, K;
    cin >> N >> K;
    map<int, int> A;
    REP(n, N) {
        int tmp;
        cin >> tmp;
        ++A[tmp];
    }
    vector<int> histo;
    for(auto kv: A) {
        histo.pb(kv.second);
    }
    sort(ALL(histo));

    auto size = SIZE(histo);
    int i = 0;
    int ans = 0;
    while(size > K) {
        ans += histo[i];
        ++i;
        --size;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 10744
#include<stdio.h>

#define free -1
#define notfree 1
#define FALSE 2
#define TRUE 3

int row[8],col[8],dpos[2*8-1],dneg[2*8-1];
int X[8][8];

void in(void);
void pri(void);
void rec(int);

int main(){
  int i,j,k,r,c;

  in();

  for(i=0;i<8;i++)
    for(j=0;j<8;j++)
      X[i][j] = FALSE;

  scanf("%d",&k);
  for(i=0;i<k;i++){
    scanf("%d %d",&r,&c);
    X[r][c] = TRUE;
  }

  rec(0);

  return 0;
}

void in(){
  int i;

  for(i=0;i<8;i++){
    row[i] = free;
    col[i] = free;
  }

  for(i=0;i<2*8-1;i++){
    dpos[i] = free;
    dneg[i] = free;
  }
}

void pri(){
  int i,j;

  for(i=0;i<8;i++)
    for(j=0;j<8;j++)
      if(X[i][j] == TRUE){
	if(row[i] != j)return;
      }

  for(i=0;i<8;i++){
    for(j=0;j<8;j++){
      if(row[i] == j)printf("Q");
      else printf(".");
    }
    printf("\n");
  }
}

void rec(int i){
  int j;

  if(i == 8){
    pri();
    return;
  }

  for(j=0;j<8;j++){
    if(notfree == col[j] || notfree == dpos[i+j] || notfree == dneg[i-j+8-1])continue;
    row[i] =j;
    col[j] = dpos[i+j] = dneg[i-j+8-1] = notfree;
    rec(i+1);
    row[i] = col[j] = dpos[i+j] = dneg[i-j+8-1] = free;
  }
}



Measured memory_bytes: 2112
#include <bits/stdc++.h>
using namespace std;
int main(){
	int A, B, M; cin >> A >> B >> M; 
	int X[100010], Y[100010]; 
	int mn1 = 200000; int mn2 = 200000; 
	for(int i = 1; i <= A; i++){
		cin >> X[i]; mn1 = min(mn1, X[i]); 
	}
	for(int i = 1; i <= B; i++){
		cin >> Y[i]; mn2 = min(mn2, Y[i]); 
	}
	int ans = mn1 + mn2; 
	for(int i = 0; i < M; i++){
		int x, y, c; cin >> x >> y >> c; 
		ans = min(ans, X[x] + Y[y] - c);  
	}
	cout << ans << endl; 
}

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

int n, m;

const int mod = 1e9 + 7;
const int N = 6e5+100;

int fac[N] = {1, 1}, rfac[N] = {1, 1}, inv[N] = {0, 1};

int C(int n, int k) {
	return 1ll * fac[n] * rfac[k] % mod * rfac[n-k] % mod;
}

int get_2(int t, int k) {
	if (t < 0) return 0;
	int up = min(n-m, t/k);
	int res = 0;
	for (int i = 0; i <= up; i ++) {
		int c = C(n-m, i);
		if (i&1) c = mod - c;
		res = (res + 1ll * c * C(n+t-k*i, n)) % mod;
	}
	return res;
}

int get(int R) {
	int res = 0;
	int up = R / m;
	for (int k = 1; k <= up; k ++) {
		res = res + get_2(R-k*m, k) - get_2(R-k*m-m, k);
		if (res < 0) res += mod;
		if (res >= mod) res -= mod;
	}
	res = 1ll * res * C(n, m) % mod;
	res = C(n+R, R) - res;
	if (res < 0) res += mod;
	return res;
}

int main() {
	int L, R;
	for (int i = 2; i < N; i ++) {
		fac[i] = 1ll * fac[i-1] * i % mod;
		inv[i] = 1ll * (mod / i) * (mod - inv[mod%i]) % mod;
		rfac[i] = 1ll * rfac[i-1] * inv[i] % mod;
	}
	scanf("%d %d %d %d", &n, &m, &L, &R);
	int ans = get(R) - get(L-1);
	if (ans < 0) ans += mod;
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 7296
{-# LANGUAGE BangPatterns #-}

module Main
  ( main
  )
where
 
import           Control.Applicative
import           Control.Monad
import           Data.Bits
import qualified Data.ByteString.Char8         as BS
import           Data.Char
import           Data.List
import           Data.Maybe
import qualified Data.Vector                   as V
 
parse = fst . fromJust
parseInt = parse . BS.readInt
parseInteger = parse . BS.readInteger
readInt = parseInt <$> BS.getLine
readInteger = parseInteger <$> BS.getLine
readIntList = map parseInt . BS.words <$> BS.getLine
readIntegerList = map parseInteger . BS.words <$> BS.getLine

res = 1000000000 + 7

main = do
  n <- readInt
  s <- getLine
  print $ count s

count (a:b:c:xs) = let score = if [a, b, c] == "ABC" then 1 else 0 in score + count (b:c:xs)
count _ = 0


Measured memory_bytes: 380
cards = input().split()

def judge(A, B):
    if (A != 1) and (B != 1):
        if A > B:
            return 'Alice'
        elif A < B:
            return 'Bob'
        else:
            return 'Draw'
    else:
        if A < B:
            return 'Alice'
        elif A > B:
            return 'Bob'
        else:
            return 'Draw'

print(judge(int(cards[0]), int(cards[1])))

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define int long long
const int MOD=1e9+7;
using pii=std::pair<int,int>;
using namespace std;

const int maxn = 1e5 + 5;

int n, m, h[maxn], a, b;
vector<int> adj[maxn];
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        cin >> h[i];
    for(int i = 0; i < m; i++)
    {
        cin >> a >> b;
        a--; b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int cnt = 0;
    for(int i = 0; i < n; i++)
    {
        int good = 1;
        for(auto v : adj[i])
            if(h[v] >= h[i])
                good = 0;
        cnt += good;
    }
    cout << cnt << "\n";
    return 0;
}

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

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

int main() {
    int n,x;
    cin >> n >> x;
    int a[n];
    rep(i,n) cin >> a[i];
    int d = 0, cnt = 1;
    rep(i,n) {
      if (d + a[i] > x) break;
      cnt++;
      d += a[i]; 
    }
    cout << cnt << endl;
    return 0;
}

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

using ll    = long long;
using ull   = unsigned long long;
using veci  = vector<int>;
using vecll = vector<ll>;
#define EPS (1e-7)
#define INF (1e9)
#define PI  (acos(-1))
#define FOR(i,a,b) for(int i = (a);i < (b); ++i)
#define REP(i,n) for(int i= 0;i<(int)(n);++i)
#define pb push_back

veci enum_div(int n){
	veci ret;
	ret.pb(1);
	for(int i=1;i*i<n;i++){
		if(n%i==0){
			ret.pb(i);
			if(i != n/i){ret.pb(n/i);}
		}
	}
	ret.pb(n);
	return ret;
}
int gcb(int a,int b){return ((b == 0)? a : gcb(b,a%b));}
int gcd(int a,int b){return (a*b) / gcb(a,b);}

int main(){
    ll a,b;
    char op;
    cin >> a >> op >> b;
    if(op =='+'){
        cout << a+b << endl;
    }else{
        cout << a-b <<endl;
    }
    return 0;
}



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

typedef long long ll;


int N = 26;
int D;

vector<int> c(N+1);
vector<vector<int>> s;
vector<int> t;

ll now_score = 0;

ll greedy(){
    vector<int> last(N+1, 0);
    ll greedy_score=0;
    for(int d = 1; d <= D; d++){
        ll max_score = -1e9;
        vector<int> max_last;
        for(int n = 1; n <= N; n++){
            ll tmp_score = 0;
            vector<int> tmp_last(N+1);
            tmp_last = last;
            
            tmp_score +=  s[d][n];
            tmp_last[n] = d;
     
            int penalty = 0;
            for(int i = 1; i <= N; i++){
                penalty += c[i]*(d-tmp_last[i]);    
                
            }
            
            tmp_score -= penalty;

            if(max_score < tmp_score){
                max_score = tmp_score;
                max_last = tmp_last;
                t[d] = n;
            }                    
            
        }
        
        last = max_last;
        greedy_score += max_score;
    }

    return greedy_score;
}


ll scoring(){
    vector<int> last(N+1, 0);
    ll score = 0;
    for(int d = 1; d <= D; d++){

        score += s[d][t[d]];
        last[t[d]] = d;

        int penalty = 0;
        for(int i = 1; i <= N; i++){
            penalty += c[i]*(d-last[i]);    
        }
        
        score -= penalty;            
    }
    return score;
}


void exchange(int d, int x){
    swap(t[d], t[d+x]);

    ll swap_score = scoring();
    
    if(now_score >= swap_score){
        swap(t[d], t[d+x]);
    }else{
        now_score = swap_score;
    }

}

void pachinko(){
    srand((unsigned) time(NULL)); /* Use Mersenne Twister */
    for(int i=1; i<=D; i++){
        int pre = t[i];
        t[i] = rand()%26+1;

        ll pachi_score = scoring();
        if(now_score >= pachi_score){
            t[i] = pre;
        }else{
            now_score = pachi_score;
        }        
    }

}

int main(){
    clock_t start = clock();

    cin>> D;

    s.resize(D+1);
    for(int i=0; i<=D; i++){
        s[i].resize(N+1);
    }
    t.resize(D+1);

    for(int i=1; i<=N; i++){
        cin>>c[i];
    }
 
    for(int i=1; i<=D; i++){
        for(int j=1; j<=N; j++){
            cin>>s[i][j];
        }
    }
    for(int i=1; i<=D; i++){
        cin>>t[i];
    }

    now_score = greedy();

    clock_t now_time = clock();
    while((now_time - start)/CLOCKS_PER_SEC < 1.2){
  
        //乱数パチンコ
        pachinko();
        now_time = clock();
        if((now_time - start)/CLOCKS_PER_SEC < 1.2){
            break;
        }
        //解交換
        for(int x=1; x<D; x++){
            for(int d=1; d<=D-x; d++){
                exchange(d, x);
            }
        }
        now_time = clock();
    }

    for(int i=1; i<=D; i++){           
        cout<<t[i]<<endl;
    }

    return 0;
}

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

using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVC vector<vector<char>>
#define fore(i,a) for(auto &i:a)

typedef pair <int, int> P;
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
const int  INF = 1 << 25;
const ll INFL = 1223372036854775807;
const ll mod = 1000000007;


struct UnionFind {
	vector<ll> par;
	ll cnt;
	UnionFind(ll size_) : par(size_, -1), cnt(size_) { }
	bool unite(ll x, ll y) {
		x = find(x); y = find(y);
		if (x != y) {
			if (par[y] < par[x]) swap(x, y);
			par[x] += par[y]; par[y] = x;
			cnt--;
		}
		return x != y;
	}
	bool same(ll x, ll y) {
		return find(x) == find(y);
	}
	ll find(ll x) {
		return par[x] < 0 ? x : par[x] = find(par[x]);
	}
	ll size(ll x) {
		return -par[find(x)];
	}
	ll size() {
		return cnt;
	}
};



int main() {
	
	ll n, m;
	cin >> n >> m;

	UnionFind uf(n);

	ll res = n * (n - 1) / 2;

	VLL v(m), w(m);

	REP(i, m) {
		cin >> v[i] >> w[i];
		v[i]--;
		w[i]--;
	}

	VLL ans(m);

	for (ll i = m - 1; i >= 0; i--) {
		ans[i] = res;
		if (uf.same(v[i], w[i]))continue;
		res -= uf.size(v[i])*uf.size(w[i]);
		uf.unite(v[i], w[i]);
	}
	
	REP(i, m)cout << ans[i] << endl;
	

	return 0;
}

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

using int64 = long long;

using vint = vector<int>;

constexpr int INF = (1 << 30) - 1;
constexpr int64 INF64 = (1ll << 60) - 1;

#define rep(i, N) for(int i=0;i<(int)(N);++i)
#define fs first
#define sc second
#define e_b emplace_back
#define m_p make_pair
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()

template <typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
	return os << "P(" << p.first << ", " << p.second << ")";
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os << "[";
	for (auto& e : v) os << e << ", ";
	return os << "]";
}
template <typename T, typename U>
ostream& operator<<(ostream& os, const map<T, U>& m) {
	os << "{" << endl;
	for (auto& e : m) os << "(" << e.first << ", " << e.second << ")" << endl;
	return os << "}";
}
template <typename T>
ostream& operator<<(ostream& os, const set<T>& s) {
	os << "{" << endl;
	for (auto& e : s) os << ", " << e << endl;
	return os << "}";
}

template<typename T>
vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template<typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v(ts...))>(a, make_v(ts...));
}

int64 gcd(int64 x, int64 y) {
	if (x == 0 || y == 0) return 0;
	int64 r;
	while ((r = y % x) != 0) {
		y = x;
		x = r;
	}
	return x;
}
int64 lcm(int64 x, int64 y) {
	if (x == 0 || y == 0) return 0;
	return x / gcd(x, y) * y;
}

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

void Main();
signed main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(30);
	Main();
}


/*----------------------------Insert from here!----------------------------*/

struct UnionFind {
	vector<int> data;

	UnionFind(int sz) {
		data.assign(sz, -1);
	}

	bool unite(int x, int y) {
		x = root(x), y = root(y);
		if (x == y) return false;
		if (data[x] > data[y]) swap(x, y);
		data[x] += data[y];
		data[y] = x;
		return true;
	}

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

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

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

/*----------------------------Insert above here----------------------------*/


void Main() {
	int n, r; cin >> n >> r;
	UnionFind tree(n);
	rep(i, n) {
		int p; cin >> p, p--;
		tree.unite(i, p);
	}

	map<int, int> m;
	rep(i, n) {
		if (tree.root(i) == i) m[tree.size(i)]++;
	}

	r = min(r, n - r);
	vint dp(r + 1, -1);
	dp[0] = 0;
	for (auto& e : m) {
		int cnt = e.sc;
		int v = e.fs;
		for (int j = 0; j <= r; ++j) {
			if (dp[j] >= 0) dp[j] = cnt;
			else if (j < v || dp[j - v] <= 0) dp[j] = -1;
			else dp[j] = dp[j - v] - 1;
		}
	}

	cout << (dp[r] > 0 ? "Yes" : "No") << endl;
}


Measured memory_bytes: 4584
n, y = gets.strip.split.map(&:to_i)
_i, _j, _k = -1, -1, -1

(0..n).each do |i|
    (0..n-i).each do |j|
       if i * 10000 + j * 5000 + (n - i - j) * 1000 == y
           _i, _j, _k = i, j, n - i - j
       end
    end
end

puts "#{_i} #{_j} #{_k}"

Measured memory_bytes: 14304
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <sstream>
#include <math.h>
#include <queue>
#include <map>
#include <set>
#include <ios>     // std::left, std::right
#include <iomanip> // std::setw(int), std::setfill(char)
using namespace std;

std::string allist="abcdefghijklmnopqrstuvwxyz";

int al_to_num(char al){
for(int i=0;i<26;++i){
  if(allist[i]==al){
    return i;
  }
}  }

int main(){
std::string s,t;
cin>>s;
cin>>t;
char target;
long long target_num;
long long s_list[26][100010]={};
vector<long long> t_list;
long long s_len=s.size();
for(int i=s_len-1;i>=0;i--){
  target=s[i];
  target_num=al_to_num(target);
  if(i==s_len-1){
    for(int j=0;j<26;++j){
      s_list[j][s_len-1]=-1;
    }
    s_list[target_num][s_len-1]=s_len-1;
  }
  else{
  for(int j=0;j<26;++j){
    if(j==target_num){
      s_list[j][i]=i;
    }
    else{
      s_list[j][i]=s_list[j][i+1];
    }
  }}
}
for(int i=0;i<t.size();++i){
  target=t[i];
  target_num=al_to_num(target);
  t_list.push_back(target_num);
}
long long ans=0;
long long next;
for(int i=0;i<t_list.size();++i){
  //targetを探しに行く
  target_num=t_list[i];
  next=s_list[target_num][ans%s_len];
  //nextが次のsの時
  if(next==-1){
    ans+=(s_len-ans%s_len);
    next=s_list[target_num][ans%s_len];
    if(next==-1){
      ans=-1;
      break;
    }
  }
  ans+=(next-ans%s_len);
  ans+=1;
}
cout<<ans<<"\n";
return 0;
}

Measured memory_bytes: 22076
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<iomanip>
using namespace std;

int main(){
    int a,b;
    cin>>a>>b;
    if(b%a==0)cout<<a+b<<endl;
    else cout<<b-a<<endl;

    return 0;
}

Measured memory_bytes: 3624
N, Q = map(int, input().split())
S = input()
l = [list(map(int, input().split())) for _ in range(Q)]
ans = [0] * (N + 1)

for i in range(2, N+1):
    if S[i-2:i] == "AC":
        ans[i] = ans[i-1] + 1
    else:
        ans[i] = ans[i-1]

for i, j in l:
    print(ans[j] - ans[i])


Measured memory_bytes: 30756
word = input()
n = int(input())
for i in range(n):
    command = list(input().split())
    temp = ""
    if command[0] == "print":
        print(word[int(command[1]):int(command[2])+1])
    elif command[0] == "reverse":
        temp += word[:int(command[1])]
        for i in range(int(command[2]), int(command[1])-1, -1):
            temp += word[i]
        temp += word[int(command[2])+1:]
        word = temp
    else:
        temp += word[:int(command[1])]
        temp += command[3]
        temp += word[int(command[2])+1:]
        word = temp


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

int main(void) {
	long long n, m; cin >> n >> m;
	long long correct = 0, penalty = 0;
	vector<vector<string>> Q(n + 10);
	long long q;
	string s;
	rep(i, m) {
		cin >> q >> s;
		q--;
		Q[q].emplace_back(s);
	}

	for (long long i = 0; i < n; i++) {
		bool flag = false;
		int sum = 0;
		for (long long j = 0; j < Q[i].size(); j++) {
			if (Q[i][j] == "WA") {
				penalty++;
				sum++;
			}
			else if (Q[i][j] == "AC") {
				correct++;
				flag = true;
				break;
			}
		}
		if (!flag) penalty -= sum;
	}

	cout << correct << " " << penalty << endl;
	return 0;
}

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

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


Measured memory_bytes: 3604
/**
 *      purpose : 
 *      author  : kyomukyomupurin
 *      created : 
**/

// input/output
#include <iostream>
#include <fstream>
#include <sstream>
// container class
#include <array>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
// math, algorithm
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
// etc
#include <bitset>
#include <cassert>
#include <cctype>
#include <cstring>
#include <chrono>
#include <iomanip>
#include <random>
#include <utility>
// using-directive
using namespace std;
// alias template
using int64 = long long;
using vi = vector<int>;
using vl = vector<int64>;
using pii = pair<int, int>;
using pll = pair<int64, int64>;
// text macro replacement
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define print(x) cout << (x) << '\n'
#define debug(x) cerr << #x << ": " << (x) << '\n'
#define dbg(v) for (size_t _ = 0; _ < v.size(); ++_){cerr << #v << "[" << _ << "] : " << v[_] << '\n';}
// variadic template
template<typename T> inline void chmin(T &a, T b) {if (a > b) a = b; return;}
template<typename T> inline void chmax(T &a, T b) {if (a < b) a = b; return;}
// constant
const int INF = (1<<30) - 1;
const int64 INF64 = (1LL<<62) - 1;
const int MOD = 1000000007;

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

  int n; cin >> n;
  vi a(n);
  iota(all(a), 1);

  do {
    for (int i = 0; i < n; ++i) {
      cout << a[i];
      if (i != n - 1) cout << " ";
    }
    cout << '\n';
  } while (next_permutation(all(a)));

  return 0;
}


Measured memory_bytes: 3136
#include <iostream>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <utility>
#include <string.h>
#include <map>
#include <stack>
#include <iomanip>
#include <chrono>
#include <random>
#include <bitset>
#include <math.h>
#include <time.h>
#include <assert.h>
#define rnd mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define pb push_back 
#define mp make_pair
#define ff first
#define ss second
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define all(x) x.begin(),x.end() 
#define PII pair <int,int>
#define N 500005
#define MOD 1000000007
#define INF 1000000000000000000
using namespace std;

int main()
{
	int n, k;
	string s;
	cin >> n >> k;
	cin >> s;
	s[k - 1] = s[k - 1] - 'A' + 'a';
	cout << s;
}	

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

int main(void)
{
	int i;
  char s[100002];
  int ans = 0;
	
	scanf("%s", s);
	
  for (i = 1; i < strlen(s); i++){
    if (s[i] == s[i-1]){
      if (s[i] == '0') {
        s[i] = '1';
        ans++;
      } else {
        s[i] = '0';
        ans++;
      }
    }
  }
  
	printf("%d", ans);
	
	return 0;
	
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
int H,W,M,i,max1,max2,k1,cc,dd1,dd2;
  max1=0;
  max2=0;
  dd1=0;
  dd2=0;
  k1=0;
  scanf("%d %d %d",&H,&W,&M);
  
  int h[M],w[M],sw[H+W];
  
  for(i=0;i<H+W;++i)
  {
  sw[i]=0;
  }
  
  for(i=0;i<M;++i)
  {
  scanf("%d %d",&h[i],&w[i]);
  sw[h[i]-1]++;
  sw[H+w[i]-1]++;
  }
  
  for(i=0;i<H;++i)
  {if(sw[i]>max1) max1=sw[i]; }
  for(i=0;i<H;++i)
  { if(sw[i]==max1) dd1++;}
  
  for(i=0;i<W;++i)
  {if(sw[H+i]>max2) max2=sw[H+i]; }
  for(i=0;i<W;++i)
  { if(sw[H+i]==max2) dd2++;}
  
  for(i=0;i<M;++i)
  {if(sw[h[i]-1]==max1 && sw[H+w[i]-1]==max2) k1++;}
  
  if(k1 == dd1*dd2) printf("%d",max1+max2-1);
  else printf("%d",max1+max2);
  
return 0;
}

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

int main() {
  int n, p;
  cin >> n >> p;
  string s;
  cin >> s;

  if (10%p == 0) {
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
      if ((s[i]-'0') % p == 0) {
        ans += i+1;
      }
    }
    cout << ans << endl;
    return 0;
  }

  vector<int> d(n+1);
  int ten = 1;
  for(int i = n-1; i >= 0; --i) {
    int mod = (s[i]-'0') * ten % p;
    d[i] = (d[i+1]+mod) % p;
    ten *= 10; ten %= p;
  }
  vector<int> cnt(p);
  long long ans = 0;
  for (int i = n; i >= 0; --i) {
    ans += cnt[d[i]];
    cnt[d[i]]++;
  }

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

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

int main(){
    int A,B;
    int ans = -1;
    cin >> A >> B;
    for(int i = 0;i<10000;i++){
        
        int a = i*0.08;
        int b = i*0.1;
        
        if(a!=0 && A == a && B == b){
            ans = i;
        break;
        }
    }
    
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define INF 1000000000
#define MAX 2000005
using ll=long long;
using Graph=vector<vector<ll>>;

ll modpow(ll a,ll n,ll mod){
  ll res=1;
  while(n>0){
    if(n&1){
      res=(res*a)%mod;
    }
    a=(a*a)%mod;
    n>>=1;
  }
  return res;
}

ll modinv(ll a,ll mod){
  return modpow(a,mod-2,mod);
}

ll fac[MAX],finv[MAX],inv[MAX];

void COMinit(){
  fac[0]=fac[1]=1;
  finv[0]=finv[1]=1;
  inv[1]=1;
  for(int i=2;i<MAX;i++){
    fac[i]=(fac[i-1]*i)%MOD;
    inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
    finv[i]=finv[i-1]*inv[i]%MOD;
  }
}

ll COM(int n,int k){
  if(n<k){
    return 0;
  }
  if(n<0||k<0){
    return 0;
  }
  return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}


int main(){
  ll K;
  cin>>K;
  string S;
  cin>>S;
  ll N=S.size();

  COMinit();

  ll n=N+K;
  ll ans=0;
  for(ll i=N;i<=n;i++){
    ll x=COM(i-1,N-1)*modpow(25,i-N,MOD)%MOD;
    x=x*modpow(26,n-i,MOD)%MOD;
    ans+=x;
    ans%=MOD;
  }

  cout<<ans<<endl;
}


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

int main(){
    int n;
    cin >> n;
    int c[n-1];
    int s[n-1];
    int f[n-1];
    for(int i=0;i<n-1;i++){
        cin >> c[i];
        cin >> s[i];
        cin >> f[i];
    }
    long long int result;
    for(int j=0;j<n-1;j++){
        result = 0;
        for(int i=j;i<n-1;i++){
            if(result <= s[i]){
                result += s[i] - result;
            }else if(result % f[i] != 0){
                result +=f[i] - (result % f[i]);
            }
            result += c[i];
        }
        cout << result << endl;
    }
    cout << 0 << endl;
}

Measured memory_bytes: 256
//逆

#include<iostream>
#include<algorithm>
#include<bitset>

#include<cmath>
#include<cstring>
#include<climits>

#include<vector>
#include<set>
#include<map>
#include<unordered_set>
//#include<unordered_map>
#include<tr1/unordered_map>

#include<fstream>
#include<chrono>

using namespace std;
using namespace std::tr1;
using namespace std::chrono;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
typedef vector<int> v32;
typedef vector<ll> v64;

const ll MOD7 = 1e9 + 7;
const ll MOD9 = 1e9 + 9;
const ll INF  = 1LL << 57LL;

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define ITER iterator
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define brep(i,s,e) for(int i=s;i>=e;i--)
#define all(x) x.begin(),x.end()
#define mem(x,y) memset(x,y,sizeof(x))
#define ones __builtin_popcount
#define DANGER std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

int main()
{
    // DANGER;
    ofstream out("output.txt");

    // ll t;
    // cin>>t;

    auto start = high_resolution_clock::now();

    ll n;
    cin>>n;
    ll a[n][3];
    rep(i,0,n-1) cin>>a[i][0]>>a[i][1]>>a[i][2];

    ll dp[n][3];
    mem( dp,0 );
    dp[0][0] = a[0][0];
    dp[0][1] = a[0][1];
    dp[0][2] = a[0][2];

    rep(i,1,n-1)
    {
        rep(j,0,2)
        {
            rep(id,0,2) if( id!=j )
            dp[i][j] = max( dp[i][j],dp[i-1][id]+a[i][j] );
        }
    }

    ll ans = 0;
    rep(i,0,2) ans = max( ans,dp[n-1][i] );
    cout<<ans<<"\n";

    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<milliseconds>(stop - start); 
    // cout << "Time taken by function: " << duration.count() << " milliseconds" << endl;
}

Measured memory_bytes: 4992
X, K, D = map(int, input().split())

if X == 0:
    print(0 if K % 2 == 0 else D)
elif X < 0:

    div = abs(X) // D
    tmp = X + D*div

    if div >= K:
        print(abs(X + D*K))
    elif div < K:
        K -= div
        print(abs(tmp) if K % 2 == 0 else abs(tmp+D))    

else:

    div = abs(X) // D
    tmp = X - D*div

    if div >= K:
        print(abs(X - D*K))
    elif div < K:
        K -= div
        print(abs(tmp) if K % 2 == 0 else abs(tmp-D))




Measured memory_bytes: 61764
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
	char s[100],a,b;
	int i,len;
	while(cin>>s)
	{
		len=strlen(s);
		for(i=0;i<len;i++)
		{a=s[0];b=s[i];}
		cout<<a<<len-2<<b<<endl;
	}
	return 0;
}


Measured memory_bytes: 256
import math

S = list(input())
K = int(input())

if len(set(S)) == 1:
  print(math.floor(len(S)*K/2))
  quit()
    
first = S[0]

a = 0
for l in S:
  if l == first:
    a+=1
  else:
    break

last = S[-1]
b = 0
for l in S[::-1]:
  if l == last:
    b+=1
  else:
    break

prev = S[a]
c = 0

for l in S[a+1:-b]:
  if prev == l:
    c += 1
    prev = ""
  else:
    prev = l

d = 0
if first == last:
  d =  math.floor((a+b)/2)
else:
  d = math.floor(a/2) +  math.floor(b/2)
ans = math.floor(a/2) + d*(K-1) + c*K + math.floor(b/2)
print(ans)

Measured memory_bytes: 3064
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;


int main(){
  ll n; cin >> n ; vl an(n); ll count = 0; bool zerocount = false;
  rep(i,n){
    ll x; cin >> x; 
    if(x < 0) count++;
    else if(x == 0) zerocount = true;
    an[i] = abs(x);
  }
  
  ll sum = 0;
  for(ll i=0; i < n; i++) sum += an[i];
  
  sort(all(an));
  
  if(zerocount) cout << sum << endl;
  else if(count % 2 == 0) cout << sum << endl;
  else cout << sum - 2*an[0] << endl;
}

Measured memory_bytes: 1024
#include <iostream>
using namespace std;
int main() {
  int n, m = 0;
  bool b = false;
  cin >> n;

  for (int i = 0; i < n; ++i) {
    int d1, d2;
    cin >> d1 >> d2;
    if (d1 == d2) {
      ++m;
    } else {
      m = 0;
    }
    if (m == 3) {
      b = true;
    }
  }
  if (b) {
    puts("Yes");
  } else {
    puts("No");
  }
  return 0;
}


Measured memory_bytes: 3680
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

template<class T> void chmin(T &a,T b) { if (a>b) a=b;}
int gcd(int a, int b){//ユークリッドの互除法
  if (a < b) gcd(b,a); //aの方がbよりでかいのが前提
  if (b == 0) return a; //aをbで割り切れたらreturn
  else gcd(b, a % b);
}
template<class T> inline bool chmax(T &a,T b){
  if (a<b){
    a=b;
    return 1;
  }
  return 0;
}

long long dp[100][2];

int main() {
  int N; ll K;
  cin >> N >> K;
  vector<ll> A(N);
  for(int i = 0; i < N; i++) cin >> A[i];
  rep(i,100) dp[i][0] = dp[i][1] = -1;
  
  dp[45][0] = 0;
  
  for(int d = 44; d >= 0; d--){
    ll mask = 1LL << d;
    int num = 0;
    rep(i,N) if(A[i] & mask) num++;
    
    if(dp[d+1][1] >= 0){
      chmax(dp[d][1],dp[d+1][1] + mask * max(num, N-num));
    }
    if(dp[d+1][0] >= 0){
      if(K & (1LL<<d)){
        chmax(dp[d][1], dp[d+1][0] + mask * num);
        chmax(dp[d][0], dp[d+1][0] + mask * (N-num));
      }else{
        chmax(dp[d][0], dp[d+1][0] + mask * num);
      }
    }
  }
  cout << max(dp[0][0], dp[0][1]) << endl;
  return 0;
}

Measured memory_bytes: 1024
#!/usr/bin/env ruby
n, k = gets.chomp.split.map(&:to_i)

arr = Array.new(n + 1, 0)

k.times do
  d = gets.chomp.to_i
  a = gets.chomp.split.map(&:to_i)

  a.each do |a_i|
    arr[a_i] += 1
  end
end

ans = -1
arr.each do |arr_i|
  ans += 1 if arr_i == 0
end

puts ans



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

int main(){
  int N ;
  cin >> N ;
  string S[110] ;
  for(int i=0;i<N;i++)
    cin >> S[i];
  string ans = "Three" ;
  for(int i=0;i<N;i++){
    if(S[i] == "Y"){
      ans = "Four";
      break ;
    }
  }
  cout << ans << endl ;
}


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


int main(){
    
    ll R,G,B,N,NN,NNN,NNNN,cnt=0;
    cin>>R>>G>>B>>N;
    NNNN=N;
    
    rep(i,0,3001){
        rep(j,0,3001){
            if((N-R*i-G*j)/B>=0 &&(N-R*i-G*j)%B==0)cnt++;
        }
    }
    cout<<cnt<<endl;
}




Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cfloat>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define int long long
#define ll long long
#define eps LDBL_EPSILON
#define mod 10000000
#define int long long
#define double long double
#define INF LLONG_MAX/10
#define P pair<int,int>
#define prique priority_queue
using namespace std;
signed main() {
	int n;
	cin >> n;
	if (log2(n) == (int)log2(n))puts("No");
	else {
		puts("Yes");
		cout << 1 + n << " " << 2 + n << endl;
		for (int i = 2; i < n; i += 2) {
			cout << 1 << " " << i << endl;
			cout << i << " " << i + 1 << endl;
			cout << 1 << " " << n + i + 1 << endl;
			cout << n + i << " " << n + i + 1 << endl;
		}
		if (n % 2 == 0) {
			int m = n ^ 1;
			for (int i = 2; i < n; i++) {
				if ((m ^ i) < n) {
					cout << n << " " << i << endl;
					cout << 2 * n << " " << (m ^ i) + n << endl;
					break;
				}
			}
		}
	}
	return 0;
}

Measured memory_bytes: 2304
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

int LCM(int m, int n) {
	int x = m*n;
	while (m%n != 0) {
		int temp = m%n;
		m = n; n = temp;
	}
	return x / n;
}

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

	int Ans = v[0];
	for (int i = 1; i < n; i++) {
		Ans = LCM(Ans, v[i]);
	}
	cout << Ans << endl;
}

Measured memory_bytes: 3180
#include<bits/stdc++.h>
#define LL long long
#define pb push_back
#define pii pair<int, int>
#define mp make_pair
using namespace std;
const int maxn = 2e5 + 10;
char s[maxn];
int main()
{
	#ifdef DEBUG
	freopen("text.in", "r", stdin);
	#endif
	int n, ans = 0;
	scanf("%d", &n); 
	scanf("%s", s + 1);
	for (int l = 1, r = n; l < r; ) {
		while (l <= n && s[l] == 'R') ++l;
		while (r && s[r] == 'W') --r;
		if (l < r) swap(s[l], s[r]), ++ans;
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 3980
//pragma
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

#define YOU using
#define DONT namespace
#define SAY std

YOU DONT SAY;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<pll> vll;

#define REPP(i,a,b,d) for(int i=a;i<=b;i+=d)
#define REP(i,a,b) REPP(i,a,b,1)
#define REVV(i,a,b,d) for(int i=a;i>=b;i-=d)
#define REV(i,a,b) REVV(i,a,b,1)

#define FOR(i,a) for(int i=0; i<a; i++)
#define FORD(i,a) for(int i=(int)a-1; i>=0; i--)

#define pb push_back
#define F first
#define S second

const int OO = 1e9;
const ll INF = 1e18;

const int irand(int lo,int hi){
	return ((double)rand()/(RAND_MAX + 1.0)) * (hi-lo+1) + lo;
}

const ll lrand(ll lo,ll hi){
	return ((double)rand()/(RAND_MAX + 1.0)) * (hi-lo+1) + lo;
}

#define getc getchar
template<typename T>
T getnum(){
	int sign = 1;
	T ret = 0;
	char c;

	do{
		c = getc();
	}while(c == ' ' || c == '\n');
	if(c == '-')sign = -1;
	else ret = c-'0';
	while(1){
		c = getc();
		if(c < '0' || c > '9')break;
		ret = 10*ret + c-'0';
	}
	return sign * ret;
}

inline void ini(int& x){
	x = getnum<int>();
}

inline void scani(int& x){
	scanf("%d",&x);
}

//end of macro


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #define endl '\n'
    cout.setf(ios::fixed);
    cout.setf(ios::showpoint);
    cout.precision(10);

    ll n;
    cin>>n;
    ll t = (n+999)/1000;
    cout << t*1000 - n << endl;

    return 0;
}


Measured memory_bytes: 3652
# include <stdio.h>
# include <bits/stdc++.h>
using namespace std;
# define fi cin
# define fo cout
# define x first
# define y second
# define ll long long
# define IOS ios_base :: sync_with_stdio(0);cin.tie(0)
# define p(v) cerr << #v << " = " << v << '\n'
# define p2(v) cerr << #v << " = " << (complex < int > (v.x,v.y)) << '\n'
# define vi vector < int >
# define vll vector < ll >
# define pii pair < int , int >
# define mp make_pair
int main(void)
{
    #ifdef CF
    freopen("input","r",stdin);
    #endif // CF
    srand(time(0));
    fo << fixed << setprecision(7);
    cerr << fixed << setprecision(7);
    int n,k;
    fi>>n>>k;
    if (k == 1 || k == n + n - 1) return puts("No") * 0;
    static int ans[1 << 20];
    ans[n] = k;
    int mn = k - 1;
    int mx = k + 1;
    auto go = [&](int i,int k)
    {
        if (!k)
            ans[i] = mn,mn = max(0,mn - 1);
        else
            ans[i] = mx,mx = min(n + n,mx + 1);
    };
    for (int i = 1;i < n;++i)
    {
        if (i & 1)
        {
            if (mn)
                go(n - i,0);
            else
                go(n - i,1);
            if (mx != n + n)
                go(n + i,1);
            else
                go(n + i,0);
        }
        else
        {
            if (mn)
                go(n + i,0);
            else
                go(n + i,1);
            if (mx != n + n)
                go(n - i,1);
            else
                go(n - i,0);
        }
    }
    fo << "Yes\n";
    for (int i = 1;i <= n + n - 1;++i)
        fo << ans[i] << '\n';
    cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
    return 0;
}

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

using namespace std;

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

    const unsigned int M = 1000000007;
    int H,W;
    cin>>H>>W;
    vector<vector<char>> grid;
    grid.resize(H, vector<char>(W));
    
    for (size_t i = 0; i < H; ++i)
    {
        for (size_t j = 0; j < W; ++j)
        {
            cin>>grid[i][j];
        }
    }

    vector<vector<int>> f;
    f.resize(H, vector<int>(W));
    for (size_t j = 0; j < W; ++j)
    {
        if(grid[0][j]!='#')
        {
            f[0][j]=1;
        }
        else {
            break;
        }
    }
    for (size_t i = 0; i < H; ++i)
    {
        if (grid[i][0]!='#') {
            f[i][0]=1;
        } else {
            break;
        }
    }

    for (size_t i = 1; i < H; ++i)
    {
        for (size_t j = 1; j < W; ++j)
        {
            if(grid[i][j]=='#') {
                f[i][j] = 0;
            } else {
                f[i][j] = (f[i-1][j] + f[i][j-1]) % M;
            }
        }
        
    }
    
    cout << f[H-1][W-1] << "\n";
}

Measured memory_bytes: 5248
from fractions import gcd
A, B, C, D = map(int, input().split())

def lcm(x, y):
    return (x * y) // gcd(x, y)

lcmv = lcm(C, D)
bc = B // C
bd = B // D
bl = B // lcmv
ac = (A-1) // C
ad = (A-1) // D
al = (A-1) // lcmv
print(B - A + 1 - ((bc + bd - bl) - (ac + ad - al)))

Measured memory_bytes: 5204
#include <cstdio>
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
const int MAX_N = 500;
const int BLOCK = 1;

struct Rect{
	int h, pos;
	Rect(int h_, int pos_){
		h = h_; pos = pos_;
	}
	Rect(){}
};

int getLargestRectangle(vector<int> buffer){
	int size = buffer.size();
	stack<Rect> S;
	int maxv = 0;
	buffer.push_back( 0 );
	
	for(int i = 0 ; i <= size ; i++ ){
		Rect rect( buffer[i] , i );
		if ( S.empty() ){
			S.push( rect );
		}else{
			if( S.top().h < rect.h ){
				S.push( rect );
			}else if( S.top().h > rect.h ){
				int target = i;
				while ( !S.empty() && S.top().h >= rect.h ){
					Rect prev = S.top(); S.pop();
					int area = prev.h * (i - prev.pos);
					maxv = max( maxv , area );
					target = prev.pos;
				}
				rect.pos = target;
				S.push(rect);
			}
		}
	}
	return maxv;
}
 
int N;
int buffer[MAX_N][MAX_N];
 
int getLargestRectangle(){
	vector<int> T[MAX_N];
	for(int i=0 ; i < N ; i++ ){
		T[i] = vector<int>(N);
	} 
	
	for(int j = 0 ; j < N ; j++ ){
		int sequence = 0;
		for(int i = 0 ; i < N ; i++ ){
			if( buffer[i][j] == BLOCK ){
				sequence = T[i][j] = 0;
			}else{
				T[i][j] = ++sequence;
			}
		}
	}
	    
	int maxv = 0;
	for(int i = 0 ; i < N ; i++ ){
		maxv = max( maxv, getLargestRectangle( T[i] ) );
	}
    
	return maxv;
}
 
int main(){
	int w, h;
	while( cin >> h >> w , w || h ){
		N = max(w,h);
		vector<string> s(h);
		for(int y=0 ; y < h ; y++ ){
			cin >> s[y];
		}
		
		for(int y = 0 ; y < N ; y++ ){
			for(int x = 0; x < N ; x++ ){
				buffer[y][x] = 1;
			}
		}
		for(int y = 0 ; y < h ; y++ ){
			for(int x = 0; x < w ; x++ ){
				buffer[y][x] = (s[y][x] == '.')? 0 : 1 ;
			}
		}
		// 0 or 1 の値の二次元配列 bufferで1のみで構成される最大の長方形の面積を出力
		cout << getLargestRectangle() << endl;
	}
}

Measured memory_bytes: 3156
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define SORT(i) sort((i).begin(), (i).end())
#define INF 2000000000
constexpr ll mod = 1e9 + 7;

int main(){
    int N, A;
    cin >> N >> A;
    int a = N % 500;
    if(A>=a){
        cout << "Yes" << "\n";
    }
    else {
        cout << "No" << "\n";
    }

    return 0;
}

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

struct RURM {
	using t1 = int;
	using t2 = int;
	static t1 id1() { return INT_MAX; }
	static t2 id2() { return -1; }
	static t1 op1(const t1& l, const t1& r) { return min(l, r); }
	static t1 op2(const t1& l, const t2& r) { return r != id2() ? r : l; }
	static t2 op3(const t2& l, const t2& r) { return r != id2() ? r : l; }
};

template <typename M>
class LazySegmentTree {
	using T1 = typename M::t1;
	using T2 = typename M::t2;
	const int h, n;
	vector<T1> data;
	vector<T2> lazy;
	void push(int node) {
		if (lazy[node] == M::id2()) return;
		if (node < n) {
			lazy[node * 2] = M::op3(lazy[node * 2], lazy[node]);
			lazy[node * 2 + 1] = M::op3(lazy[node * 2 + 1], lazy[node]);
		}
		data[node] = M::op2(data[node], lazy[node]);
		lazy[node] = M::id2();
	}
public:
	LazySegmentTree(int n_)
		: h(ceil(log2(n_))), n(1 << h), data(n * 2, M::id1()), lazy(n * 2, M::id2()) {}
	LazySegmentTree(int n_, T1 v1, T2 v2)
		: h(ceil(log2(n_))), n(1 << h), data(n * 2, v1), lazy(n * 2, v2) {}
	LazySegmentTree(const vector<T1>& data_)
		: h(ceil(log2(data_.size()))), n(1 << h), data(n * 2, M::id1()), lazy(n * 2, M::id2()) {
		init(data_);
	}
	void init() {
		for (int i = n - 1; i >= 1; i--) data[i] = M::op1(data[i * 2], data[i * 2 + 1]);
	}
	void init(const vector<T1>& data_) {
		for (int i = 0; i < (int)data_.size(); i++) data[i + n] = data_[i];
		init();
	}
	void update(int l, int r, T2 val) {
		l += n, r += n;
		for (int i = h; i > 0; i--) push(l >> i), push(r >> i);
		int tl = l, tr = r;
		r++;
		while (l < r) {
			if (l & 1) lazy[l] = M::op3(lazy[l], val), l++;
			if (r & 1) r--, lazy[r] = M::op3(lazy[r], val);
			l /= 2; r /= 2;
		}
		while (tl > 1) {
			tl >>= 1, tr >>= 1;
			if (lazy[tl] == M::id2()) data[tl] = M::op1(M::op2(data[tl * 2], lazy[tl * 2]), M::op2(data[tl * 2 + 1], lazy[tl * 2 + 1]));
			if (lazy[tr] == M::id2()) data[tr] = M::op1(M::op2(data[tr * 2], lazy[tr * 2]), M::op2(data[tr * 2 + 1], lazy[tr * 2 + 1]));
		}
	}
	T1 find(int l, int r) {
		l += n, r += n;
		for (int i = h; i > 0; i--) push(l >> i), push(r >> i);
		r++;
		T1 res1 = M::id1(), res2 = M::id1();
		while (l < r) {
			if (l & 1) res1 = M::op1(res1, M::op2(data[l], lazy[l])), l++;
			if (r & 1) r--, res2 = M::op1(M::op2(data[r], lazy[r]), res2);
			l /= 2; r /= 2;
		}
		return M::op1(res1, res2);
	}
};

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int n, q, com, x, y, val;
	cin >> n >> q;
	LazySegmentTree<RURM> st(n);
	while (q--) {
		cin >> com >> x >> y;
		if (com) {
			printf("%d\n", st.find(x, y));
		}
		else {
			cin >> val;
			st.update(x, y, val);
		}
	}
	return 0;
}

Measured memory_bytes: 5124
#include<iostream>
using namespace std;
long long a,b,n,m;
int T;
long long floorsum(long long a,long long b,long long n,long long m){
	long long ans = 0;
	if (a >= m) {
		ans += (n - 1) * n * (a / m) / 2;
		a %= m;
	}
	if (b >= m) {
		ans += n * (b / m);
		b %= m;
	}
 
	long long y_max = (a * n + b) / m;
	long long x_max = y_max * m - b;
	if (y_max != 0) {
		ans += (n - (x_max + a - 1) / a) * y_max;
		ans += floorsum(m, (a - x_max % a) % a, y_max, a);
	}
 
	return ans;
}
int main(){
	cin>>T;
	while(T--){
		cin>>n>>m>>a>>b;
		cout<<floorsum(a,b,n,m)<<endl;
		
	}
}

Measured memory_bytes: 3572
#include <bits/stdc++.h>
#define N 100020
#define ll long long
using namespace std;
inline int read(){
  int x=0,f=1;char ch=getchar();
  while(ch>'9'||ch<'0')ch=='-'&&(f=0)||(ch=getchar());
  while(ch<='9'&&ch>='0')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
  return f?x:-x;
}
int main(int argc, char const *argv[]) {
  int n = read(), k = read();

  if (k == 1 || k == 2 * n - 1) {
    return puts("No"), 0;
  }

  puts("Yes");

  if (n == 2) {
    return printf("1\n2\n3\n"), 0;
  }

  if (k == 2) {

    for (int i = 1; i <= n - 2; ++ i) {
      printf("%d\n", i + 4);
    }

    printf("3\n2\n1\n4\n");

    for (int i = 1; i <= n - 3; ++ i) {
      printf("%d\n", i + n + 2);
    }

    return 0;

  }

  int cnt = 1;

  for (int i = 1; i <= n - 2; ++ i){
    if (cnt == k - 2) {
      cnt = k + 2;
    }
    printf("%d\n", cnt ++);
  }

  printf("%d\n%d\n%d\n%d\n", k-1, k, k+1, k-2);

  for (int i = 1; i <= n - 3; ++ i) {
    if (cnt == k - 2) {
      cnt = k + 2;
    }
    printf("%d\n", cnt ++);
  }

  return 0;
}
/*

如果 k == 1 || k == 2*n-1 无解（显然）。

    x
   0xx
  00xx0
 000xx00
000000000

如果在中间列出现了两个连续的x，那么最终结果一定是x。

所以只要构造中间四个即可。。

  (x-1) x (x+1) (x-2)

注意如果 x == 2

  (x+1) x (x-1) (x+2)
    3   2   1     4

*/

Measured memory_bytes: 1536
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define MT make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define RT return
#define vv(a,b,c,d) vector<vector<a> >(b,vector<a>(c,d))
#define vvv(a,b,c,d,e) vector<vector<vector<a> > >(b,vv(a,c,d,e))
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    const int MA = 100005;
    int N;
    cin >> N;
    vi A(N);
    rep(i, N)cin >> A[i];
    int T = accumulate(all(A), 0);

    bitset<MA> cur, nex;
    cur[0] = 1;
    rep(i, N) {
        nex.reset();
        rep(j, MA)if (cur[j]) {
            int x = j + A[i];
            int y = abs(j - A[i]);
            if (x < MA)nex[x] = 1;
            if (y < MA)nex[y] = 1;
        }
        swap(cur, nex);
    }
    rep(i, MA) if (cur[i]) {
        int x = (T - i) / 2;
        int y = T - x;
        cout << max(x, y) << endl;
        return 0;
    }
}

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

int dp[100005];

int helper(int arr[], int i, int n){
    if(i >= n){
        return 0;
    }
    
    if(dp[i] != -1){
        return dp[i];
    }
    
    // take left
    
    int left = 0;
    
    if(i + 1 <= n)
        left = helper(arr, i+1, n) + abs(arr[i+1] - arr[i]);
    
    
    int right = 0;
    if(i + 2 <= n)
        right = helper(arr, i + 2, n) + abs(arr[i+2] - arr[i]);
    
    return dp[i] = min(left, right);
    
}

int main(){
    int n;
    cin >> n;
    int arr[n];
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }
    
    memset(dp, -1, sizeof(dp));
    cout << helper(arr, 0, n) << endl;
    
}

Measured memory_bytes: 7296