akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>

using namespace std;
typedef long long ll;
ll mod = 1000000007;

int main() {
    string s;
    cin>>s;
    for (int i = 0; i < s.size(); i++) {
        if (i % 2 == 0) {
            if (s[i] != 'R' && s[i] != 'U' && s[i] != 'D') {
                printf("No\n");
                return 0;
            }
        } else {
            if (s[i] != 'L' && s[i] != 'U' && s[i] != 'D') {
                printf("No\n");
                return 0;
            }
        }
    }
    printf("Yes\n");
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp(x) fixed << setprecision(x)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const int inf = (1<<30)-1;
const ll INF = (1LL<<60)-1;
const ld EPS = 1e-10;
template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};
template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};

int main(){
    int N, A, B;
    cin >> N >> A >> B;
    B ^= A;
    int n = __builtin_popcount(B);
    if(!(n&1)) {cout << "NO" << endl; return 0;}
    cout << "YES" << endl;
    vector<int> st;
    rep(i, 1<<N) st.pb(i&(-i));
    vector<int> sub;
    sub.pb(0), sub.pb(1);
    rep2(i, 1, n-1){
        sub.pb(1<<i);
        rep2(j, 1, (1<<i)-1){
            if(st[j] == 1) sub.pb(1<<(i-1));
            elif(st[j] == (1<<(i-1))) sub.pb(1);
            else sub.pb(st[j]);
        }
    }
    vector<int> ans;
    int now = 0;
    for(auto &e: sub){
        now ^= e;
        ans.pb(now);
        rep2(j, 1, (1<<(N-n))-1) {
            now ^= (st[j]<<n);
            ans.pb(now);
        }
    }
    vector<int> zero, one;
    rep(i, N){
        if(B&(1<<i)) one.pb(i);
        else zero.pb(i);
    }
    for(auto &e: ans){
        int res = 0;
        rep(i, n){
            if(e&(1<<i)) res |= (1<<one[i]);
        }
        rep(i, N-n){
            if(e&(1<<(n+i))) res |= (1<<zero[i]);
        }
        cout << (res^A) << ' ';
    }
    cout << endl;
}

Measured memory_bytes: 2200
#include <cstdio>
#include <algorithm>
#include <complex>
using namespace std;

int main() {
  for(int tci = 0; ; tci++) {
    complex<double> ps[3];
    complex<double> pp;
    int rr = scanf("%lf%lf%lf%lf%lf%lf%lf%lf",
        &ps[0].real(), &ps[0].imag(),
        &ps[1].real(), &ps[1].imag(),
        &ps[2].real(), &ps[2].imag(),
        &pp.real(), &pp.imag());
    if(rr<8) break;
    bool ok = true;
    for(int i = 0; i < 3; i++) {
      double det1 = imag( (ps[(i+1)%3]-ps[i]) * conj(pp-ps[i]) );
      double det2 = imag( (ps[(i+2)%3]-ps[i]) * conj(pp-ps[i]) );
      if(det1 * det2 > 1e-9) {
        ok = false;
      }
    }
    printf("%s\n", ok ? "YES" : "NO");
  }
  return 0;
}

Measured memory_bytes: 1044
n,m,c=map(x->parse(Int,x),split(readline()))
b=map(x->parse(Int,x),split(readline()))
ans=0
for i=1:n
	s=c
	a=map(x->parse(Int,x),split(readline()))
	for j=1:m
		s+=b[j]*a[j]
	end
	if s>0
		ans+=1
	end
end
print(ans)

Measured memory_bytes: 123856
from collections import Counter

N = int(input())

index = 0
even_numbers = []
odd_numbers = []

for i in input().split():
    if index % 2 == 0:
        even_numbers.append(int(i))
    else:
        odd_numbers.append(int(i))
    index += 1

even = Counter(even_numbers).most_common(2)
odd = Counter(odd_numbers).most_common(2)

if even[0][0] == odd[0][0]:
    if len(even) == 1:
        print(N//2)
    else:
        print(N - even[0][1] - max(even[1][1], odd[1][1]))
else:
    print(N - even[0][1] - odd[0][1])


Measured memory_bytes: 15332
#include <iostream>
#include <queue>
#include <vector>

const char BLACK_CHAR = '#';
const char WHITE_CHAR = '.';

int main() {
	int H, W;
	std::cin >> H >> W;

	std::vector<std::vector<char>> s(H, std::vector<char>(W));
	int numWhite = 0;
	for(int h = 0; h < H; h++) {
		for(int w = 0; w < W; w++) {
			std::cin >> s[h][w];
			if(s[h][w] == WHITE_CHAR) {
				numWhite++;
			}
		}
	}

	std::vector<std::vector<bool>> checked(H, std::vector<bool>(W, false));
	struct StepPoint {
		int x, y;
		int step;
	};
	std::queue<StepPoint> queue;
	queue.push(StepPoint{0, 0, 0});
	checked[0][0] = true;
	
	int step = -1;
	while(!queue.empty()) {
		const StepPoint sp = queue.front();
		queue.pop();

		if(sp.x == W - 1 && sp.y == H - 1) {
			step = sp.step;
			break;
		}

		for(int d = -1; d <= 1; d += 2) {
			for(bool toX : {true, false}) {
				const int nx = sp.x + (toX ? d : 0);
				const int ny = sp.y + (toX ? 0 : d);
				const bool inRange = (0 <= nx && nx < W && 0 <= ny && ny < H);
				if(inRange
					&& s[ny][nx] == WHITE_CHAR
					&& !checked[ny][nx]) {
					checked[ny][nx] = true;
					queue.push(StepPoint{nx, ny, sp.step + 1});
				}
			}
		}
	}

	const int numWhiteOnRoad = step + 1;
	const int result = numWhite - numWhiteOnRoad;
	std::cout << (step == -1 ? -1 : result) << std::endl;

	return 0;
}

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

template<typename T>
ostream& operator<<(ostream &os, vector<T> &v){
	string sep = " ";
	if(v.size()) os << v[0];
	for(int i=1; i<v.size(); i++) os << sep << v[i];
	return os;
}

template<typename T>
istream& operator>>(istream &is, vector<T> &v){
	for(int i=0; i<v.size(); i++) is >> v[i];
	return is;
}

#ifdef DBG
void debug_(){ cout << endl; }
template<typename T, typename... Args>
void debug_(T&& x, Args&&... xs){
	cout << x << " "; debug_(forward<Args>(xs)...);
}
#define dbg(...) debug_(__VA_ARGS__)
#else
#define dbg(...)
#endif

int main() {
	ios_base::sync_with_stdio(false);
	cout << setprecision(20) << fixed;

	int n, k; cin >> n >> k;
	vector<ll> a(n); cin >> a;

	for(int i=0; i<n-k; i++){
		if(a[i] < a[i+k]){
			cout << "Yes" << endl;
		} else {
			cout << "No" << endl;
		}
	}
	return 0;
}


Measured memory_bytes: 4844
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
using namespace std;

#define MAX 10000
vector<int> vx, vy;
bool dp[2][MAX * 2+1]; //0は本番

bool check(int a, vector<int> &v) {
	for (int i = 0; i < v.size(); i++) {
		for (int j = 0; j <= MAX * 2; j++) { //到達可能j
			if (!dp[0][j]) continue;
			if (j - v[i] >= 0) dp[1][j - v[i]] = true;
			if (j + v[i] <= 20000) dp[1][j + v[i]] = true;
			//dp[0][j] = false;
		}
		swap(dp[0], dp[1]);
		fill(dp[1], dp[1]+MAX * 2+1, false);
	}
	return dp[0][a + MAX];
}

int main() {
	int i, cnt, x, y;
	string s;
	cin >> s;
	cin >> x >> y;
	int turn = 0; //x座標
	int l = 0, r = 0, sz = s.size();
	while (l < sz) {
		while (r < sz && s[r] == 'F') r++;
		if (l == 0) {
			dp[0][r - l + MAX] = true;
		}
		else if(turn % 2==0){ //x座標
			vx.push_back(r - l);
		}
		else { //y座標
			vy.push_back(r - l);
		}
		turn++;
		l = ++r;
	}

	bool x_yes = check(x, vx);
	fill(dp[0], dp[0]+MAX*2+1, false); 
	dp[0][MAX] = true;
	bool y_yes = check(y, vy);
	if (x_yes && y_yes) cout << "Yes" << endl;
	else cout << "No" << endl;	
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
const int MX=2e5+5;
int n,m1,m2,x[MX],y[MX],a[MX];
bool cmp1(int &i,int &j){
    return x[i]+y[i]>x[j]+y[j];
}
bool cmp2(int &i,int &j){
    return x[i]-y[i]>x[j]-y[j];
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for(int i=0; i<n; i++) cin >> x[i] >> y[i],a[i]=i;
    sort(a,a+n,cmp1);
    m1 = abs(x[a[0]]-x[a[n-1]]) + abs(y[a[0]]-y[a[n-1]]);
    sort(a,a+n,cmp2);
    m2 = abs(x[a[0]]-x[a[n-1]]) + abs(y[a[0]]-y[a[n-1]]);
    cout << max(m1,m2);
    return 0;
}

Measured memory_bytes: 5884
A,B = map(int, input().split())		# 5 7 2

ans=-1

for i in range(1,1001):
	a = int(i * 0.08)
	if A!=a: continue
	
	b = int(i * 0.1)
	if B!=b: continue
	
	ans=i
	break

print(ans)



Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T&a,T&b){if(a<b){a=b;return true;}return false;}
template<class T> inline bool chmin(T&a,T&b){if(a>b){a=b;return true;}return false;}
const ll INF = 1LL<<60;
const ll M = 1000000007;
/**/

int main(){
    ll x,y;cin>>x>>y;
    if(y%2==0 && y-2*x>=0 && 4*x-y>=0){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    return 0;
}


Measured memory_bytes: 3640
n = input()
num_list = list(map(int, n))
k = int(input())

dp = [[[0] * (k+2) for _ in range(2)] for _ in range(len(n)+1)]
dp[0][0][0] = 1
for i, v in enumerate(num_list):
    for j in range(k+1):
        dp[i+1][1][j] += dp[i][1][j]
        dp[i+1][1][j+1] += dp[i][1][j] * 9

        if v == 0:
            dp[i+1][0][j] += dp[i][0][j]
        else:
            dp[i+1][1][j+1] += dp[i][0][j] * (v - 1)
            dp[i+1][1][j] += dp[i][0][j]
            dp[i+1][0][j+1] += dp[i][0][j]

print(dp[len(n)][0][k] + dp[len(n)][1][k])

Measured memory_bytes: 38384
#include <iostream>
using namespace std;
int main(void){
    int a,b,c,d,e,k;
    scanf("%d", &a);
    scanf("%d", &b);
    scanf("%d", &c);
    scanf("%d", &d);
    scanf("%d", &e);
    scanf("%d", &k);
    if(e-a <= k){
        printf("Yay!");
    }else{
        printf(":(");
    }
    return 0;
}


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

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

bool rev(char color, int y, int x, int cc, vector<vector<char> > &b) {
  if (b[y][x] == color) {
    return true;
  }

  if (b[y][x] == '.') {
    return false;
  }

  bool flag = rev(color, y + dy[cc], x + dx[cc], cc, b);
  if (flag) {
    b[y][x] = color;
  }

  return flag;
}

int canRevN(char color, int y, int x, int cc,
	    const vector<vector<char> > &b, int depth) {
  if (b[y][x] == color) {
    return 0;
  }

  if (b[y][x] == '.') {
    return -depth;
  }

  return canRevN(color, y + dy[cc], x + dx[cc], cc, b, depth + 1) + 1;
}

int main() {
  vector<vector<char> > b(10);
  for (int y = 0; y < 10; y++) {
    b[y].resize(10);
    fill(b[y].begin(), b[y].end(), '.');
  }

  for (int y = 1; y <= 8; y++) {
    for (int x = 1; x <= 8; x++) {
      cin >> b[y][x];
    }
  }

  char color = 'o';
  int lastMaxN = -1;
  int maxN = -1;

  while (maxN != 0 || lastMaxN != 0) {
    lastMaxN = maxN;
    maxN = 0;

    int maxY = -1;
    int maxX = -1;

    const int oval[] = {1, 2, 3, 4, 5, 6, 7, 8};
    const int xval[] = {8, 7, 6, 5, 4, 3, 2, 1};

    for (int i = 0; i < 8; i++) {
      for (int j = 0; j < 8; j++) {
	int y = color == 'o' ? oval[i] : xval[i];
	int x = color == 'o' ? oval[j] : xval[j];

	if (b[y][x] != '.') {
	  continue;
	}

	int n = 0;
	for (int cc = 0; cc <= 7; cc++) {
	  n += canRevN(color, y + dy[cc], x + dx[cc], cc, b, 0);
	}

	if (n > maxN) {
	  maxN = n;
	  maxY = y;
	  maxX = x;
	}
      }
    }

    if (maxN != 0) {
      for (int cc = 0; cc <= 7; cc++) {
	b[maxY][maxX] = color;
	rev(color, maxY + dy[cc], maxX + dx[cc], cc, b);
      }
    }

    color = color != 'o' ? 'o' : 'x';
  }

  for (int y = 1; y <= 8; y++) {
    for (int x = 1; x <= 8; x++) {
      cout << b[y][x];
    }
    cout << endl;
  }

  return 0;
}

Measured memory_bytes: 3096
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
string s;
int l;
int main()
{
    cin>>s;
    l=s.size();
    for(int i=0;i<l;i++)
    {
        if(s[i]=='C')
        {
            for(int j=i+1;j<l;j++)
            {
                if(s[j]=='F')
                {
                    cout<<"Yes";
                    return 0;
                }
            }
        }
    }
    cout<<"No";
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<map>
#include<numeric>
#include<set>
#include<string>
#include<utility>
#include<vector>

#define rep(i, a, n)  for(int i=a; i<n; i++)
#define per(i, a, n)  for(int i=n-1; i>=a; i--)
#define fill0(n)  setfill('0') << right << setw(n)
#define all(x)  (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define MAX 1000001
using namespace std;
typedef long long ll;

int main(){
  int n=3;
  vector<int> path(4, 0);
  rep(i, 0, n){
    int a, b; cin >> a >> b;
    a--;  b--;
    path[a]++;
    path[b]++;
  }
  int edge = 0, between = 0;
  rep(i, 0, 4){
    if(path[i]==1)  edge++;
    else if(path[i]==2) between++;
  }
  if(edge==2 && between==2) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        int cnt2 = 0;
        int cnt4 = 0;
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }

        for (int i = 0; i < n; i++) {
            if (a[i] % 4 == 0) {
                cnt4++;
                continue;
            }
            if (a[i] % 2 == 0) {
                cnt2++;
            }
        }
        if (cnt2 == 0 && cnt4 >= n / 2
                || cnt2 != 0 && cnt4 >= (n - cnt2 + 1) / 2) {
            System.out.println("Yes");
            return;
        }
        System.out.println("No");
    }

}


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

int main() {
	int n,a=1,b=1;
	cin>>n;
	for(int i=0;i<n;i++){
		if(i%2==0){
			a=a+b;
		}
		else{
			b=b+a;
		}
	}
	
	if(n%2==0){
		cout<<a<<endl;
	}
	else{
		cout<<b<<endl;
	}
	
	return 0;
}


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

using ll=long long;
#define int ll

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(a>b)a=b;}

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

template<class t,class u>
ostream& operator<<(ostream&os, const pair<t,u>&p){
	return os<<"{"<<p.a<<","<<p.b<<"}";
}

template<class t> ostream&operator <<(ostream&os,const vc<t>&v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}

template<class t>
void mkuni(vc<t>&v){
	sort(all(v));
	v.erase(unique(all(v)),v.ed);
}

const int inf=LLONG_MAX/3;

struct BIT{
	vi buf;
	int s;
	BIT(int n=0){init(n);}
	void init(int n){buf.assign(s=n,0);}
	void add(int i,int v){
		for(;i<s;i+=(i+1)&(-i-1))
			buf[i]+=v;
	}
	int kth(int&k){
		int res=0;
		for(int i=16;i>=0;i--){
			int w=res+(1<<i);
			if(w<=s&&buf[w-1]<=k){
				k-=buf[w-1];
				res=w;
			}
		}
		return res;
	}
};

struct ysp{
	vi x;
	void init(vi xx){
		x=xx;
		sort(all(x));
	}
	int cnt(int v){
		int w=1,res=0;
		rep(_,19){
			int z=(w+v-1)/v;
			if(z==1)
				res+=x.size();
			else if(z<=1000000000)
				res+=x.ed-lower_bound(all(x),z);
			if(_<18)w*=10;
		}
		return res;
	}
};

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	
	int n,m;cin>>n>>m;
	vi a(n),b(m);
	rep(i,n)cin>>a[i];
	rep(i,m)cin>>b[i];
	
	vi sum(n);
	{
		ysp mrt;mrt.init(b);
		rep(i,n){
			int s=mrt.cnt(a[i]);
			sum[i]=s;
		}
		rep(i,n-1)
			sum[i+1]+=sum[i];
	}
	dmp(sum);
	vc<ysp> kh(m);
	{
		vvc<int> buf(m);
		rep(i,m){
			for(int x=i;x<m;x+=(x+1)&(-x-1))
				buf[x].pb(b[i]);
		}
		rep(i,m)
			kh[i].init(buf[i]);
	}
	int q;cin>>q;
	string ans(q,'x');
	vc<tuple<int,int,int>> adi;
	rep(i,q){
		int d;cin>>d;
		d--;
		int r=upper_bound(all(sum),d)-sum.bg;
		if(r==n){
			continue;
		}
		if(r>0)d-=sum[r-1];
		adi.eb(a[r],d,i);
	}
	int s=adi.size();
	sort(all(adi));
	vi as(s);
	rep(i,s)as[i]=get<0>(adi[i]);
	vvc<int> qs(s+1);
	rep(i,m){
		int w=1;
		rep(_,19){
			int z=(w+b[i]-1)/b[i];
			qs[lower_bound(all(as),z)-as.bg].pb(i);
			if(_<18)w*=10;
		}
	}
	BIT bit(m);
	rep(ii,s){
		for(auto j:qs[ii])
			bit.add(j,1);
		int av,d,i;tie(av,d,i)=adi[ii];
		int c=bit.kth(d);
		ans[i]=to_string(av*b[c])[d];
	}
	cout<<ans<<endl;
}



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

int main(){
	int N, K;
	cin >> N >> K;
	int ans = K;
	rep(i,N-1) ans *= K-1;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3628
s1=input()
s2=input()
dp=[0]*(len(s1)+1)
dp[0]=[0]*(len(s2)+1)
for i in range(1,len(s1)+1):
	dp[i]=[0]*(len(s2)+1)
	for j in range(1,len(s2)+1):
		if s1[i-1]==s2[j-1]:
			dp[i][j]=dp[i-1][j-1]+1
		else:
			dp[i][j]=max(dp[i-1][j],dp[i][j-1])
# for i in range(len(s1)+1):
# 	print(dp[i])
s=""
i,j=len(s1),len(s2)
while(i>0 and j>0):
	if s1[i-1]==s2[j-1]:
		s+=s1[i-1]
		i-=1
		j-=1
	elif dp[i][j-1]>dp[i-1][j]:
		j-=1
	else:
		i-=1
print(s[::-1])

Measured memory_bytes: 112092
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
char a[444];
int n;
int main() {
  ios::sync_with_stdio(false);
  cin>>n>>a+1;
  vector<int>f(333,0);
  int ans=0;
  for(int i=1;i+2<=n;i++){
    if(a[i]=='A'&&a[i+1]=='B'&&a[i+2]=='C')ans++;
  }
  cout<<ans<<endl;
  return 0;
}

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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	ll N,M,V,P;
	cin >> N >> M >> V >> P;
	vector<ll> A(N);
	for(auto &x:A) cin >> x;
	sort(A.begin(), A.end());

	ll ok = N-1, ng = -1;
	while(ok-ng>1){
		ll mid = (ok+ng)/2;
		ll rest = V*M-M;
		ll morebig = 0;
		for(int i=N-1;i>=0;i--){
			if(i==mid)continue;
			if(A[i]>A[mid] && morebig<P-1){
				morebig++;
				rest -= M;
			}else if(A[i]>A[mid]+M){
				rest = 1;
				break;
			}else if(rest){
				rest -= min(M,A[mid]+M-A[i]);
			}
		}
		if(rest<=0){
			ok = mid;
		}else{
			ng = mid;
		}
	}
	cout << N-ok << endl;
}

Measured memory_bytes: 1152
H, W = map(int, input().split())
s_list = []
for i in range(H):
    s = list(input())
    s_list.append(s)

dp = [[0 for _ in range(W)] for _ in range(H)]
dp[0][0] = 1
mod = 10 ** 9 + 7
for i in range(H):
    for j in range(W):
        if s_list[i][j] == "#":
            continue
        if i + 1 < H and s_list[i + 1][j] == ".":
            dp[i + 1][j] += dp[i][j] % mod
        if j + 1 < W and s_list[i][j + 1] == ".":
            dp[i][j + 1] += dp[i][j] % mod
print(dp[H - 1][W - 1] % mod)


Measured memory_bytes: 91740
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <map>
#include <utility>
#include <numeric>
#include <typeinfo>

using namespace std;

int main(){
  string S;
  cin >> S;
  reverse(S.begin(),S.end());
  for(int i=0;i<S.size();){
    if(S.at(i)=='m' && S.at(i+1)=='a' && S.at(i+2)=='e' && S.at(i+3)=='r' && S.at(i+4)=='d')  i+=5;
    else if(S.at(i)=='r' && S.at(i+1)=='e' && S.at(i+2)=='m' && S.at(i+3)=='a' && S.at(i+4)=='e' && S.at(i+5)=='r' && S.at(i+6)=='d')  i+=7;
    else if(S.at(i)=='e' && S.at(i+1)=='s' && S.at(i+2)=='a' && S.at(i+3)=='r' && S.at(i+4)=='e')  i+=5;
    else if(S.at(i)=='r' && S.at(i+1)=='e' && S.at(i+2)=='s' && S.at(i+3)=='a' && S.at(i+4)=='r' && S.at(i+5)=='e')  i+=6;
    else{
      cout << "NO" << endl;
      return 0;
    }
  }
  cout << "YES" << endl;

  return 0;
}


Measured memory_bytes: 512
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#define ri register
#define inf 0x7fffffff
#define E (1)
#define mk make_pair
#define int long long
using namespace std; const int N=5010;
inline int read()
{
	int s=0, w=1; ri char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') w=-1; ch=getchar(); }
	while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48), ch=getchar(); return s*w;
}
int n,dp[N]; struct Node{int h,p; }e[N];
inline bool cp(Node x,Node y) { return x.h+x.p<y.h+y.p; }
signed main()
{
	n=read();
	for(ri int i=1;i<=n;i++) e[i].h=read(), e[i].p=read();
	sort(e+1,e+1+n,cp); int res=0;
	for(ri int i=1;i<=n;i++) dp[i]=1e16;
	for(ri int i=1;i<=n;i++)
	for(ri int j=i;j;j--)if(e[i].h>=dp[j-1])dp[j]=min(dp[j],dp[j-1]+e[i].p);
	for(ri int i=0;i<=n;i++)if(dp[i]<1e16)res=i; printf("%lld\n",res);
	return 0;
}

Measured memory_bytes: 3840
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <math.h>
#include <queue>

using namespace std;

typedef long long int ll;
typedef long double ld;

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define vsort(a) sort(a.begin(), a.end())
#define rev(a) reverse(a.begin(), a.end())

const int MOD = 1000000007;
const int INF = INT_MAX;


// a,bの最小公倍数
ll lcm(ll a, ll b){ll lcm = a * b; ll r = a % b;while(r != 0){a = b; b = r; r = a % b;}return lcm /= b;}
// a,bの最大公約数
ll gcd(ll a, ll b){ll r = a % b;while(r != 0){a = b; b = r; r = a % b;}return b;}
// MOD
ll modadd(ll a, ll b){return (a%MOD+b%MOD+MOD)%MOD;}
ll modmul(ll a, ll b){return a%MOD*b%MOD%MOD;}
ll modexp(ll a, ll n){if(n==0)return 1; if(n%2==0){ll e=modexp(a,n/2); return modmul(e,e);} return modexp(a,n-1)*a%MOD;}
ll modinv(ll n){return modexp(n%MOD,MOD-2);}
ll modfact(ll n){ll res=1; for (int i=1; i <= n; ++i){res *= i; res %= MOD;} return res;}
ll modncr(ll n, ll r){ll numer=1;ll denom=1;for(int i=1;i<=r;++i){numer=modmul(numer,n-r+i);denom=modmul(denom,i);}return modmul(numer, modinv(denom));}



int main(){

    int n;
    cin >> n;

    int ans;
    if (n%2 == 0) ans = n/2;
    else ans = n/2 + 1;

    cout << ans << endl;



}



//              g++ -std=c++1z


Measured memory_bytes: 888
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = Integer.parseInt(sc.next());
		sc.close();

		//Nの3乗を出力
		System.out.println((int)Math.pow(N, 3));
	}
}

Measured memory_bytes: 20692
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>
#include <iomanip>
#define intt long long

int main() {
	intt H, W; std::cin >> H >> W;
	std::vector<std::vector<char>> M(H+2, std::vector<char>(W+2));
	for (int i = 1; i < H+1; ++i)
		for (int j = 1; j < W+1; ++j)
			std::cin >> M[i][j];
	for (int i = 1; i < H + 1; ++i) {
		for (int j = 1; j < W + 1; ++j) {
			if (M[i][j] == '#') {
				if (M[i - 1][j] != '#' && M[i][j - 1] != '#' && M[i + 1][j] != '#' && M[i][j + 1] != '#') {
					std::cout << "No" << std::endl;
					return 0;
				}
			}
		}
	}
	std::cout << "Yes" << std::endl;

	return 0;
}

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

int main() {
  int K ;
cin >> K;
if (K == 1) {
  cout << "ACL" << endl;
}
else if (K==2) {
  cout << "ACLACL" << endl;
}
else if (K==3) {
  cout << "ACLACLACL" << endl;
}
else if (K==4) {
  cout << "ACLACLACLACL" << endl;
}
else if (K==5) {
  cout << "ACLACLACLACLACL" << endl;
}





return 0;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
main()
{
    string s;
    cin>>s;
    int a,ans=10000;
  	int n=s.size(); 
    for(int i=0;i<n-2;i++)
    {
        a=100*(s[i]-'0')+10*(s[i+1]-'0')+s[i+2]-'0';
        if(ans>abs(753-a))ans=abs(753-a);
    }
    cout<<ans<<endl;
}

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

int selectionSort(int array[], int n);

int main(void)
{
	// ????´???°???????????????
	int n;
	scanf("%d", &n);

	// ????´????????´?????????????????????¢?????????????¢????
	int *array;
	array = (int *)malloc(n * sizeof(int));
	if (array == NULL) {
		printf("error: failed to allocate memory space\n");
		return 1;
	}

	// ????´?????????????????´?
	int i;
	for (i=0; i<n; i++) {
		scanf("%d", &array[i]);
	}

	// ????????????????????????
	int swap_cnt;
	swap_cnt = selectionSort(array, n);

	// ?????????????????????
	for (i=0; i<n; i++) {
		printf("%d", array[i]);
		if (i<n-1)
			putchar(' ');
	}
	putchar('\n');
	printf("%d\n", swap_cnt);

	free(array);
	
	return 0;
}


// ???????????????
// ???????????¶???array???0<=x<=100???n????????´??°x???????´???????????????????1<=n<=100
// ???????????¶???array???????´????????????????????????????????????????swap_cnt????????????????????°(>=0)???????´????????????????
int selectionSort(int array[], int n)
{
	int i, j, min_idx, swap_cnt=0, temp;
	for (i=0; i<n-1; i++) {
		min_idx = i;
		for (j=i; j<n; j++) {
			if (array[j] < array[min_idx]) {
				min_idx = j;
			}
		}
		if (min_idx != i) {
			swap_cnt++;
			temp = array[i];
			array[i] = array[min_idx];
			array[min_idx] = temp;
		}
	}
	return swap_cnt;
}

/*
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_B&lang=jp
*/

Measured memory_bytes: 2728
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1LL << 60;
const int mod = 1e9 + 7;

long double calc(long double x1, long double x2, long double y1, long double y2)
{
    long double dis = 0;
    long double dx = x1 - x2;
    long double dy = y1 - y2;
    dis = sqrt(pow(dx, 2) + pow(dy, 2));
    return dis;
}

int main()
{
    long double ans = 0;
    int n;
    cin >> n;
    vector<vector<long double>> xy(n, vector<long double>(2));
    for (int i = 0; i < n; i++)
    {
        cin >> xy.at(i).at(0);
        cin >> xy.at(i).at(1);
    }

    vector<vector<long double>> distance(n, vector<long double>(n));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            distance.at(i).at(j) = calc(xy.at(i).at(0), xy.at(j).at(0), xy.at(i).at(1), xy.at(j).at(1));
        }
    }

    vector<int> p(n);
    for (int i = 0; i < n; i++)
    {
        p.at(i) = i;
    }
    int num = 0;

    do
    {
        long double sum = 0;
        for (int i = 0; i < n; i++)
        {
            if (i != n - 1)
            {
                sum += distance.at(p.at(i)).at(p.at(i + 1));
            }
            else
            {
                break;
            }
        }
        ans += sum;
        num++;

    } while (next_permutation(p.begin(), p.end()));
    ans /= num;
    cout << std::fixed << std::setprecision(10) << ans << endl;
}

Measured memory_bytes: 3812
#include <math.h>

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define PI 3.14159265358979323846264338327950L
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define SIZE_OF_ARRAY(array) (sizeof(array) / sizeof(array[0]))

int main() {
  int A, B, X;

  cin >> A >> B >> X;

  if (X < A)
    cout << "NO" << endl;

  else if (X - A <= B)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
}


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

#define X first
#define Y second

using namespace std;

const int N=100;
int n,k;

int cnt;
pair<int,int> Edge[N*N/2];

void Print()
{
	printf("%d\n",cnt);
	for(int k=1;k<=cnt;k++)
		printf("%d %d\n",Edge[k].X,Edge[k].Y);
}

int main()
{
	scanf("%d %d",&n,&k);
	int num=(n-1)*(n-2)/2;
	if(k>num)
	{
		printf("-1\n");
		return 0;
	}
	
	for(int i=2;i<=n;i++)
		Edge[++cnt]=make_pair(1,i);
	if(num>k)
	{
		for(int i=2;i<=n;i++)
			for(int j=i+1;j<=n;j++)
			{
				Edge[++cnt]=make_pair(i,j);
				if( --num == k )
				{
					Print();
					return 0;
				}
			}
	}
	Print();
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void){
	long n,k,a,b;
	long ans[100001]={},cnt=0;
	for(scanf("%lld %lld",&n,&k);n;n--){
		scanf("%d %d",&a,&b);
		ans[a]+=b;
	}
	for(n=0;n<=100000;n++){
		cnt+=ans[n];
		if(k<=cnt){printf("%lld",n);return 0;}
	}
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vb = vector<bool>;
using vc = vector<char>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using pii = pair<int, int>;
#define fix10 cout << fixed << setprecision(10);
#define rep(i,n) for(int i=0; i<(int)(n);i++)

int main(){
  long n;
  cin >> n;
  vector<long> a(n);
  rep(i,n){
    cin >> a.at(i);
  }
  long sum = 0;
  long ans1 = 0;
  rep(i,n){
    sum += a.at(i);
    if(i % 2 == 0 && sum < 1){
      ans1 += 1 - sum;
      sum = 1;
    }
    if(i % 2 == 1 && sum > -1){
      ans1 += sum + 1;
      sum = -1;
    }
  }
  
  sum = 0;
  long ans2 = 0;
  rep(i,n){
    sum += a.at(i);
    if(i % 2 == 1 && sum < 1){
      ans2 += 1 - sum;
      sum = 1;
    }
    if(i % 2 == 0 && sum > -1){
      ans2 += sum + 1;
      sum = -1;
    }
  }
  cout << min(ans1,ans2) << endl;
}

Measured memory_bytes: 1024
using System;

class Program
{
    static void Main()
    {
        string[] s;
        int a, b;
        int ret;

        while (true)
        {
            s = Console.ReadLine().Split(' ');
            if (s[1] == "?") break;

            a = int.Parse(s[0]);
            b = int.Parse(s[2]);

            if (s[1] == "+")
                ret = a + b;
            else if (s[1] == "-")
                ret = a - b;
            else if (s[1] == "*")
                ret = a * b;
            else if (s[1] == "/")
                ret = a / b;

            Console.WriteLine(ret.ToString());
        }
    }
}


Measured memory_bytes: 9168
import java.util.Scanner;
     
     
    public class Main {
        

        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            int k = sc.nextInt();
 
                    if (a >= k) {
            System.out.println(k);
        } else if (a + b >= k) {
            System.out.println(a);
        } else if (a + b + c >= k) {
            System.out.println(a - (c - ((a + b + c) - k)));
        }

            
            
        }
    }

Measured memory_bytes: 35556
import java.util.Scanner;
public class Main{
 public static void main(String[] Args){
   Scanner sc = new Scanner(System.in);
   int[] ant = new int[6]; 
   for(int i = 0;i<6;i++){
     ant[i] = Integer.parseInt(sc.next());
   }
   int result = 0;
   boolean hantei = false;
   for(int i = 0;i<5;i++){
     if(hantei){
       break;
     }
     for(int j = 0;j<i;j++){
       result = ant[i]-ant[j];
       if(result>ant[5]){
         hantei = true;
         break;
       }
     }
   }
   if(hantei){
     System.out.print(":(");
   }else{
     System.out.print("Yay!");
   }
 }
}

Measured memory_bytes: 22740
__asm__ ( "\
        .comm   b,1,1              \n\
.L0:                               \n\
        .string \"%c\"             \n\
        .globl  main               \n\
main:                              \n\
        pushq   %rbp               \n\
        leaq    b(%rip), %rsi      \n\
        leaq    .L0(%rip), %rdi    \n\
        call    __isoc99_scanf@PLT \n\
        movzbl  b(%rip), %eax      \n\
        cmpl    $65, %eax          \n\
        je      .LA                \n\
        cmpl    $67, %eax          \n\
        je      .LC                \n\
        cmpl    $71, %eax          \n\
        je      .LG                \n\
        movl    $65, %edi          \n\
        jmp     .LEND              \n\
.LA:                               \n\
        movl    $84, %edi          \n\
        jmp     .LEND              \n\
.LC:                               \n\
        movl    $71, %edi          \n\
        jmp     .LEND              \n\
.LG:                               \n\
        movl    $67, %edi          \n\
.LEND:                             \n\
        call    putchar@PLT        \n\
        movl    $0, %eax           \n\
        popq    %rbp               \n\
        ret                        \n"
);

Measured memory_bytes: 128
//Ruthless Coding 
#include <bits/stdc++.h>

#define uni(x)      (x).resize(unique(all(x)) - (x).begin())
#define fprint(v)   for(auto x : v) cout << x << ' '
#define ALL(x)      (x).begin(), (x).end()
#define MP(x, y)    make_pair(x, y)
#define PII         pair<int, int>
#define SZ(x)       int((x).size())
#define PB(x)       push_back(x)
#define ll          long long
#define S           second 
#define F           first
#define nl          '\n'

using namespace std;
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...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
mt19937_64 rnd;

const int N = 2e5 + 5;

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;
    cin >> n;
    map<string, int> mp;
    for(int i = 0; i < n; i++){
        string x;
        cin >> x;
        mp[x]++;
    }
    int m;
    cin >> m;
    for(int i = 0; i < m; i++){
        string x;
        cin >> x;
        mp[x]--;
    }
    int ans = 0;
    for(auto &x: mp){
        ans = max(ans, x.S);
    }
    cout << ans;
    return 0;
}
/*
    *** Most Impo.. -> check base case always
    1. Overflow Check (*, +)
    2. Index check (0 - based or 1 - based)
    3. Check for n = 1, 2, 3, 4....
    4. Corner Cases
*/

Measured memory_bytes: 256
#include<cstdio>
#include<map>
#include<vector>
using namespace std;
struct p
{
    int to;
    int dis;
};
vector<p>w[100009];
int val[100009];
void dfs(int x,int sign,int fa)
{
    for(int i=0;i<w[x].size();i++)
    {
        p now=w[x][i];
        if(now.to==fa)
            continue;
        if(now.dis%2==0)
            val[now.to]=sign;
        else
            val[now.to]=!sign;
        dfs(now.to,val[now.to],x);
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n-1;i++)
    {
        int q,w1,e;
        scanf("%d%d%d",&q,&w1,&e);
        w[q].push_back(p{w1,e});
        w[w1].push_back(p{q,e});
    }
    val[1]=1;
    dfs(1,1,0);
    for(int i=1;i<=n;i++)
        printf("%d\n",val[i]);
    return 0;
}


Measured memory_bytes: 9088
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define repLRE(i, l, r) for (ll i = (l); i <= (r); ++i)
#define rrepLRE(i, l, r) for (ll i = (l); i >= (r); --i)
#define Sort(v) sort(v.begin(), v.end())
#define rSort(v) sort(v.rbegin(), v.rend())
#define Reverse(v) reverse(v.begin(), v.end())
#define Lower_bound(v, x) \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vT = vector<T>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;
using dqll = deque<ll>;

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

/* Macros reg. ends here */

const ll INF = 1LL << 50;
static const long long mod = 1000000007;

int main() {
  // ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(15);
 
  ll n;
  cin >> n;

  map<ll, ll> mp;
  ll ans = 0;
  rep(i,n){
    ll a;
    cin >> a;
    mp[a]++;
    ans += a;
  }

  ll q;
  cin >> q;
  rep(i, q){
    ll b, c;
    cin >> b >> c;
    if(mp.count(c)) ans -= c*mp[c];
    if(mp.count(b)) ans -= b*mp[b];
    if(mp.count(b)) {
      mp[c] += mp[b];
      mp[b] = 0;    
    }
    if(mp.count(c)) ans += c*mp[c];
    cout << ans << endl;
  }
 
  return 0;
}


Measured memory_bytes: 8632
#include<cstdio>
#include<cstring>
using namespace std;

int main(){
    char x[1001];

    while(1){
        scanf("%s", x);

        if(x[0] == '0')break;

        int total = 0;
        for(int i = 0; i < strlen(x); i++){
            int num;
            num = x[i] - '0';
            total += num;
        }

        printf("%d\n", total);
    }

    return 0;
}


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

#define READ                freopen("in.txt", "r", stdin)
#define WRITE               freopen("out.txt", "w", stdout)

#define si(a)               scanf("%d", &a)
#define sii(a,b)            scanf("%d %d", &a, &b)
#define siii(a,b,c)         scanf("%d %d %d", &a, &b, &c)

#define CLR(a)              memset(a, 0, sizeof(a))
#define SET(a)              memset(a, -1, sizeof(a))

#define PI                  acos(-1.0)

#define pb                  push_back
#define mp                  make_pair
#define SORT(v)             sort(v.begin(), v.end())
#define REV(v)              reverse(v.begin(), v.end())
#define FOR(i, n)           for(int i=0; i<n; i++)
#define FOR1(i, n)          for(int i=1; i<=n; i++)
#define ROF(i, n)           for(int i=n-1; i>=0; i--)
#define ROF1(i, n)          for(int i=n; i>=1; i--)
#define LOOP(i, x, y)       for(int i=x; i<=y; i++)
#define fastIO()            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);


typedef long long              LL;
typedef unsigned long long     ULL;
typedef vector<int>            VI;
typedef pair<int, int>         PII;
typedef pair<string, int>      PSI;
typedef pair<char, int>        PCI;

const int MAX = 100005;
const LL LMAX = 12158598925;
const double eps = 1e-9;
const int INF = 0x3f3f3f3f;

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int kx[] = {1, 1, 2, 2, -1, -1, -2, -2};
int ky[] = {2, -2, 1, -1, 2, -2, 1, -1};

int n, w;
int arr[MAX][3];
LL dp[MAX][3];



int main()
{
//    READ;
//    WRITE;
    si(n);

    for(int i=1; i<=n; i++){
        for(int j=0; j<3; j++)
            si(arr[i][j]);
    }

    for(int j=0; j<3; j++) dp[1][j] = arr[1][j];

    for(int i=2; i<=n; i++){
//        cout << "FOR: " << i << ":\n";
        for(int j=0; j<3; j++){
            LL mx = INT_MIN;
            for(int q=0; q<3; q++){
                if(q == j) continue;

                mx = max(mx, dp[i-1][q]);
            }

            dp[i][j] = arr[i][j] + mx;
//              cout << " max: " << mx << " arr: " << arr[i][j] << " dp: " << dp[i][j] << endl;
        }
//        cout << endl;
    }

//    cout << endl;
//    for(int i=1; i<=n; i++){
//        for(int j=0; j<3; j++){
//            cout << dp[i][j] << " ";
//        }
//        cout << endl;
//    }

    LL ans = INT_MIN;
    for(int j=0; j<3; j++) ans = max(ans, dp[n][j]);

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


Measured memory_bytes: 3712
def power(x, y, p) : 
    res = 1     # Initialize result 
  
    # Update x if it is more 
    # than or equal to p 
    x = x % p  
      
    if (x == 0) : 
        return 0
  
    while (y > 0) : 
          
        # If y is odd, multiply 
        # x with result 
        if ((y & 1) == 1) : 
            res = (res * x) % p 
  
        # y must be even now 
        y = y >> 1      # y = y/2 
        x = (x * x) % p 
          
    return res 
def ncr(n, r, p): 
    # initialize numerator 
    # and denominator 
    num = den = 1 
    for i in range(r): 
        num = (num * (n - i)) % p 
        den = (den * (i + 1)) % p 
    return (num * pow(den, p - 2, p)) % p 
n,a,b=map(int,input().split())
m=10**9+7;
ans=power(2,n,m)
ans-=ncr(n,a,m)
ans-=ncr(n,b,m)
print(ans%m-1)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#include <string.h>
#include <map>
#define MEM(var, val) memset(var, (val), sizeof(var))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define nitro                         \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define mod 1000000007
//*max_element(a.begin(), a.end())
vector<string>mat;
vector<vll>dp;
ll h,w;
ll paths(ll i,ll j)
{
    if(i>h-1||j>w-1)
    return 0;
    if(i==h-1&&j==w-1)
    return 1;
    if(mat[i][j]=='#')
    return 0;
    ll &ans=dp[i][j];
    if(ans!=-1)
    return ans;
    ans=paths(i+1,j)+paths(i,j+1);
    ans=ans%mod;
    return ans;
}
int main()
{
    
    cin>>h>>w;
    mat.clear();
    mat.resize(h);
    dp.clear();
    dp.resize(h);
    for(int i=0;i<h;i++)
    cin>>mat[i];
    for(int i=0;i<h;i++)
    dp[i].resize(w,-1);
    cout<<paths(0,0);

}

Measured memory_bytes: 13340
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<algorithm>
#include<utility>
#include<tuple>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<numeric>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define BIL ((ll)1e9)
#define MOD ((ll)1e9+7)
#define INF (1LL<<60)           //1LL<<63でオーバーフロー
#define inf (1<<29)             //1<<29でオーバーフロー

int main(int argc,char* argv[]){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);

    ll k,a,b;
    cin >> k >> a >> b;

    if(a+2>=b){
        cout << k+1 << endl;
    }else{
        ll q=(k-a+1)/2;
        ll r=k-(a-1+2*q);
        ll ans=a+(b-a)*q+r;
        cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 3616
/**
 *      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 <unordered_map>
#include <unordered_set>
#include <vector>
// math, algorithm
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
// etc
#include <bitset>
#include <cctype>
#include <cstring>
#include <chrono>
#include <iomanip>
#include <random>
#include <utility>
// using-directive
using namespace std;
// alias template
using int64 = int64_t;
using pii = pair<int, int>;
using pll = pair<int64_t, int64_t>;
// 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 PB push_back
#define EB emplace_back
#define MP make_pair
#define fi first
#define se second

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

  int n, m, c; cin >> n >> m >> c;

  int b[m];
  rep(i, m) cin >> b[i];
  int a[n][m];

  rep(i, n){
    rep(j, m){
      cin >> a[i][j];
    }
  }

  int ans = 0;

  rep(i, n){
    int temp = 0;
    rep(j, m){
      temp += a[i][j] * b[j];
    }
    if (temp + c > 0) ++ans;
  }

  print(ans);


  return 0;
}

Measured memory_bytes: 256
using System;
class Program
{
	static void Main(string[] args)
	{
		string[] input = Console.ReadLine().Split(' ');
        int r = int.Parse(input[0]);
        double l = 2*r*Math.PI;
		Write(l.ToString());
	}

	static void Write(string output)
	{
		Console.WriteLine(output);
	}

	static void Write(object[] output)
	{
		foreach (var o in output)
		{
			Write(o.ToString());
		}
	}
}

Measured memory_bytes: 27460
import fractions as f
a,b,c,d = map(int,input().split())
i = abs((a-1)//c-b//c)
j = abs((a-1)//d-b//d)

def lcm(x,y):
  return (x*y)//f.gcd(x,y)
l = lcm(c,d)
k = abs((a-1)//l-b//l)
print(b-a+1-(i+j-k))

Measured memory_bytes: 5180
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//cout<<fixed<<setprecision(12);
	ll n; cin>>n;
	vector <ll> arr(n);
	for (ll i = 0; i < n; ++i){
		cin>>arr[i];
	}
	vector<ll> zero_end(n);
	for (int i = 0; i < n; ++i)
		zero_end[i] = -1;
	for (ll i = 0; i < n; ++i)
	{
		// if(zero_end[i] != -1)
		// 	continue;
		if(arr[i] == 0){
			ll start = i;
			while(arr[i] == 0 && i < n){
				i++;
			}
			i--;
			zero_end[start] = i;
			for(int j = start; j <= zero_end[start]; j++)
				zero_end[j] = zero_end[start];
		}
	}
	// for (int i = 0; i < n; ++i)
	//{
		// cout<<i<<": "<<zero_end[i]<<endl;
	// }
	ll answer = 0;
	for (ll i = 0; i < n; ++i)
	{
		ll sum = arr[i], xorr = arr[i];
		ll counter = 1;
		ll j = i + 1;
		while(counter < 23 && j < n){
			if(arr[j] == 0)
			{
				j = zero_end[j] + 1;
				continue;
			}
			//cout<<"in "<<i<<" "<<j<<" "<<(sum + arr[j])<<" "<<(xorr ^ arr[j])<<endl;
			if((sum + arr[j]) != (xorr ^ arr[j])){
				//cout<<"broken\n";
				break;
			}
			else{
				sum = sum + arr[j];
				xorr = xorr ^ arr[j];
				counter++;
				j++;
			}
		}
		j--;
		// cout<<"final j "<<j<<" "<<arr[j]<<endl;
		ll this_size = j - i + 1;
		// answer += this_size*(this_size - 1)/2;
		answer += this_size - 1;
		// cout<<i<<" "<<arr[i]<<": "<<xorr<<" "<<sum<<" "<<this_size - 1<<" "<<j<<" "<<answer<<endl;
		// i = j;
	}
	cout<<answer + n<<endl;
	return 0;
}

Measured memory_bytes: 3456
#include <iostream>

using namespace std;

int main() {
	int n, x;
	while (cin >> n >> x && (n || x)) {
	  int ans = 0;
	  for (int i = 1; i <= n; ++i)
		for (int j = i + 1; j <= n; ++j)
		  for (int k = j + 1; k <= n; ++k)
			if (i + j + k == x) ans++;
	  cout << ans << endl;
	}
	return 0;
}



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

vector<vector<int>> g;

vector<bool> marked;

void dfs(int v) {
	marked[v] = true;
	for (int u: g[v]) if (!marked[u]) dfs(u);
}

int main() {
	int n, m;
	cin >> n >> m;
	g.resize(n);
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	marked.resize(n);
	int components = 0;
	for (int i = 0; i < n; i++) if (!marked[i]) {
		dfs(i);
		components++;
	}
	cout << components - 1 << '\n';

	return 0;
}

Measured memory_bytes: 9308
A,B,C,X,Y = list(map(int,input().split()))
if A+B <= 2*C:
    print(A*X+B*Y)
    exit()
if X == Y:
    print(2*C*X)
elif X > Y:
    tmp = 2*C*Y
    X -= Y
    m = min(2*C*X,A*X)
    print(tmp+m)
else:
    tmp = 2*C*X
    Y -= X
    m = min(2*C*Y,B*Y)
    print(tmp+m)

Measured memory_bytes: 3064
#include <stdio.h>
int main(){
	int i;   
	char s[4];
	scanf("%s",&s);
	for(i=0;i<3;i++){
		if(s[i]=='1'){
			s[i]='9';
		}else{
			s[i]='1';
		}
	}
	printf("%s\n",s);
	return 0;
}	

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
#include <climits>
#define ll long long
#define MAX 25 * 1e13
#define N  200010

using namespace std;
int MOD = 1000000007;

int main(){
  int n;
  cin >> n;
  int ret = 0;
  ret = n / 2;
  if( n % 2 == 1 ){
    ret++;
  }
  cout << ret << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
 
void search(char *t, char *s)
{
  int M = 0, N = 0;
  M = strlen(t);
  N = strlen(s);
  int i, j;
  
  for (i = 0; i <= N - M; i++){
    for (j = 0; j < M; j++)
      if (s[i+j] != t[j])  break;
 
    if (j == M)  printf("%d\n", i);
  }
}
  
int main()
{
  char s[1000], t[1000];

  scanf("%s", s);
  scanf("%s", t);
  
  search(t, s);
  return 0;
}

Measured memory_bytes: 548