akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-
# abc151/abc151_c
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N, M = i2nn()
    wa_list = [0] * N
    penalty = 0
    ac = 0
    for _ in range(M):
        p, S = i2s().split(' ')
        p = int(p) - 1
        if wa_list[p] >= 0:
            if S == 'WA':
                wa_list[p] += 1
            else:
                penalty += wa_list[p]
                wa_list[p] = -1
                ac += 1
    print(ac, penalty)
    return

main()


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

int N, M, Q;
string S[2000];
// the number of blue points in [0, i] \times [0, j].
int blue_count[2000][2000];
// the number of horizontal edges in [0, i] \times [0, j]
int h_edge_count[2000][2000];
int v_edge_count[2000][2000];

int main(){
    cin >> N >> M >> Q;
    for(int i = 0; i < N; i++){
        cin >> S[i];
    }
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            if(S[i][j] == '1'){
                blue_count[i][j]++;
            }
            if(i > 0 && S[i-1][j] == '1' && S[i][j] == '1'){
                v_edge_count[i][j]++;
            }
            if(j > 0 && S[i][j-1] == '1' && S[i][j] == '1'){
                h_edge_count[i][j]++;
            }
        }
    }
    for(int i = 0; i < N; i++){
        for(int j = 1; j < M; j++){
            blue_count[i][j] += blue_count[i][j-1];
            v_edge_count[i][j] += v_edge_count[i][j-1];
            h_edge_count[i][j] += h_edge_count[i][j-1];
        }
    }
    for(int j = 0; j < M; j++){
        for(int i = 1; i < N; i++){
            blue_count[i][j] += blue_count[i-1][j];
            v_edge_count[i][j] += v_edge_count[i-1][j];
            h_edge_count[i][j] += h_edge_count[i-1][j];
        }
    }
    for(int q = 0; q < Q; q++){
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        x1--; y1--; x2--; y2--;
        int blues = blue_count[x2][y2];
        if(x1 > 0){
            blues -= blue_count[x1-1][y2];
        }
        if(y1 > 0){
            blues -= blue_count[x2][y1-1];
        }
        if(x1 > 0 && y1 > 0){
            blues += blue_count[x1-1][y1-1];
        }
        int v_edges = v_edge_count[x2][y2] - v_edge_count[x1][y2];
        if(y1 > 0){
            v_edges -= v_edge_count[x2][y1-1];
            v_edges += v_edge_count[x1][y1-1];
        }
        int h_edges = h_edge_count[x2][y2] - h_edge_count[x2][y1];
        if(x1 > 0){
            h_edges -= h_edge_count[x1-1][y2];
            h_edges += h_edge_count[x1-1][y1];
        }
        
        cout << blues - v_edges - h_edges<< endl;
    }
    
    
}



Measured memory_bytes: 52736
using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <climits>
#include <bitset>
#include <array>
#include <deque>
#include <queue>
#include <map>
#define all(x) (x).begin(),(x).end()

void solve(){

}
int main(){
    map<char,int> symbol;

    symbol.insert(make_pair('+',0));
    symbol.insert(make_pair('-',0));

    string s;
    cin >> s;
    for (int i = 0; i < (int)s.size(); i++){
        symbol[s[i]]++;
    }

    cout << symbol['+'] - symbol['-'] << endl;


    return 0;
}


Measured memory_bytes: 256
n = int(input())
lis = []
ans = 0
for i in range(n):
    inp = int(input())
    if inp % 10 == 0:
        ans += inp
    else:
        lis.append(inp)
if not lis:
    print("0")
    exit()
if sum(lis) % 10 == 0:
    print(ans + sum(lis) - min(lis))
    exit()
print(ans + sum(lis))

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

int main() {
  char c;
  cin>>c;
  
  if(c=='a'){
  cout<<"vowel";
  }
  else if(c=='i'){
  cout<<"vowel";
  }
  else if(c=='u'){
  cout<<"vowel";
  }
  else if(c=='e'){
  cout<<"vowel";
  }
  else if(c=='o'){
  cout<<"vowel";
  }
  else{
  
  cout<<"consonant";
  }
  
}


Measured memory_bytes: 256
def f(v,e):
  for x in v:
    if len(e[x]) == 1:#端であるなら、プラス1して次へ
      y = e[x][0]
      v.remove(x)#returnで終わるから
      e[x] = []
      e[y].remove(x)
      return f(v,e)+1
  return 0 #端じゃないなら0
#与えられるグラフは連結なので、これでよい。
  
n,m = map(int,input().split())
v = list(range(1,n+1))
e = [[]]*(n+1)
for _ in [0]*m:
  x,y = map(int,input().split())
  e[x] = e[x] + [y]
  e[y] = e[y] + [x]
print(f(v,e))

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

typedef long long ll;
int n;
ll d[10001],v[10001],k[10001],res[10001];

ll gcd(ll a,ll b){
	if(b==0)return a;
	return gcd(b,a%b);
}

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

int main(void){
	while(1){
		scanf("%d",&n);
		if(n==0)break;
		for(int i=0;i<n;i++){
			scanf("%lld%lld",&d[i],&v[i]);
			ll G=gcd(d[i],v[i]);
			d[i]/=G;
			v[i]/=G;
		}
		ll dist=lcm(d[0],d[1]);
		for(int i=2;i<n;i++)dist=lcm(dist,d[i]);
		for(int i=0;i<n;i++)k[i]=dist/d[i]*v[i];
		ll t=gcd(k[0],k[1]);
		for(int i=2;i<n;i++)t=gcd(t,k[i]);
		for(int i=0;i<n;i++)res[i]=k[i]/t;
		for(int i=0;i<n;i++)printf("%lld\n",res[i]);
	}
	return 0;
}

Measured memory_bytes: 1044
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        
        Scanner scan = new Scanner(System.in);
        int number1 = scan.nextInt();
        int number2 = scan.nextInt();
        int number3 = scan.nextInt();
        
        int multiplier = scan.nextInt();
        
        int [] data = {number1,number2,number3};
        
        int maxnumber = 0;
        
        for(int i = 0; i < data.length; i++){
            maxnumber = Math.max(maxnumber,data[i]);
        }
        
        int max = maxnumber;
        
        for (int count = 0 ; count < multiplier ; count++){
            max = max * 2;
        }
        
        int ans = number1 + number2 + number3 + max - maxnumber;
 
        System.out.println(ans);
        
    }
}

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

int n,k;
int a[100005],dp[100005];

int main(){

    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];

    dp[1]=0;

    for(int i=2;i<=n;i++){

        dp[i]=dp[i-1]+abs(a[i]-a[i-1]);

        for(int j=i-2;j>=max(1,i-k);j--)

            dp[i]=min(dp[i],dp[j]+abs(a[i]-a[j]));

    }

    cout<<dp[n];

}


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

/*
ll dp[3010][3010];
 
ll lcs(string s, string t){
    int n,m;
    n = s.size();
    m = t.size();
    rep(i,n+1){
        dp[i][0] = 0;
    }
    rep(j,m+1){
        dp[0][j] = 0;
    }
 
 
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(s[i-1]==t[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
            else if(dp[i-1][j] > dp[i][j-1]) dp[i][j]=dp[i-1][j];
            else dp[i][j]=dp[i][j-1]; 
        }
    }
    return dp[n][m];
}
*/

ll dp[5010][5010];

void solve(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    rep(i,n){
      dp[i][0]=0;
      dp[0][i]=0;
    }
    for(int i=1; i<=n; i++){
      for(int j=1; j<=n; j++){
        if(i>=j) dp[i][j]=0;
        else if(s[i-1]==s[j-1] && i + dp[i-1][j-1]<j) dp[i][j] = dp[i-1][j-1]+1;
        else dp[i][j]=0;

        //cout << i << " " << j << " " << dp[i][j] << endl;
      }
    }
    ll ma = 0;
    rep(i,n){
      rep(j,n){
        ma = max(ma, dp[i+1][j+1]);
      }
    }
    cout << ma << endl;
}

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

Measured memory_bytes: 196096
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
//#include<boost/multiprecision/cpp_int.hpp>
//#include<boost/multiprecision/cpp_dec_float.hpp>
//namespace mp=boost::multiprecision;
//#define mulint mp::cpp_int
//#define mulfloat mp::cpp_dec_float_100
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
//constexpr int MOD=1000000007;
constexpr int MOD=998244353;
#define INF (1<<30)
#define LINF (lint)(1LL<<56)
#define endl "\n"
#define rep(i,n) for(lint (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(lint (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
#define fi first
#define se second
typedef long long lint;
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
const int MAX_N=2e5+5;

struct edge{lint to,cost;};
lint V;
vector<edge> G[200000]; // MAX_V
lint d[200000]; // MAX_V
void dijkstra(lint S){
  priority_queue<plint,vector<plint>,greater<plint>> que;
  fill(d,d+V,LINF);
  d[S]=0;
  que.push(plint(0,S));
  while(!que.empty()){
    plint p=que.top();
    que.pop();
    lint v=p.second;
    if(d[v]<p.first) continue;
    rep(i,G[v].size()){
      edge e=G[v][i];
      if(d[e.to]>d[v]+e.cost){
        d[e.to]=d[v]+e.cost;
        que.push(plint(d[e.to],e.to));
      }
    }
  }
}

int main(void){
    int n,m,s,t;
    cin >> n >> m >> s >> t;
    s--,t--;
    V=n;
    lint u[m],v[m],a[m],b[m];
    lint yen[n],snuuk[n];
    rep(i,m) cin >> u[i] >> v[i] >> a[i] >> b[i];
    rep(i,m) u[i]--,v[i]--;
    rep(i,m){
        edge in;
        in.to=v[i],in.cost=a[i];
        G[u[i]].push_back(in);
        in.to=u[i];
        G[v[i]].push_back(in);
    }
    dijkstra(s);
    rep(i,n) yen[i]=d[i];
    rep(i,n) G[i].clear();
    rep(i,m){
        edge in;
        in.to=v[i],in.cost=b[i];
        G[u[i]].push_back(in);
        in.to=u[i];
        G[v[i]].push_back(in);
    }
    dijkstra(t);
    rep(i,n) snuuk[i]=d[i];
    multiset<lint> dis;
    rep(i,n) dis.insert(yen[i]+snuuk[i]);
    rep(i,n){
        cout << 1000000000000000-*dis.begin() << endl;
        auto itr=dis.find(yen[i]+snuuk[i]);
        dis.erase(itr);
    }
}

Measured memory_bytes: 23516
#include <stdio.h>

int main(void){
  int n, k;
  scanf("%d", &n);
  char s[n];
  scanf("%s", s);
  scanf("%d", &k);

  char point = s[k-1];
  
  for(int i=0; i<n; i++){
    if(s[i]!=point){ s[i]='*';}
  }

  printf("%s \n", s);
  return 0;
}



Measured memory_bytes: 128
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 23 09:58:34 2019

@author: Yamazaki Kenichi
"""

A, B, C, D = map(int,input().split())

def gcd(x, y):
    while y != 0:
        x, y = y, x%y
    return x

cd = C * D // gcd(C, D)

ans = 0
ans += B // C + B // D - B // cd
ans -= (A-1) // C + (A-1) // D - (A-1) // cd
ans = B - A + 1 -ans 
print(ans)


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

int main(){
  int A,B,H,M;
  cin >> A >> B >> H >> M;
  
  //0:00からの角度
  double A_rad,B_rad;
  double PI = 3.14159265358979;
  A_rad = ((2.0 * PI) / (double)(12 * 60)) * (double)(H * 60 + M);
  B_rad = ((2.0 * PI) / (double)60) * (double)M;
  //cout << A_rad << endl;
  //cout << B_rad << endl;
  
  double henkaku,h1,h2;
  h1 = A_rad - B_rad;
  h2 = B_rad - A_rad;
  //cout << h1 << ", " << h2 << endl;
  if(h1 < h2){
    henkaku = h1;
  }else{
    henkaku = h2;
  }
  //cout << henkaku << endl;
  
  double ret2,ret;
  ret2 = A*A + B*B - 2 * A * B * cos(henkaku);
  ret = sqrt(ret2);
  cout << fixed << setprecision(20);
  cout << ret << endl;
  
}

Measured memory_bytes: 4176
#include <bits/stdc++.h>
#define fin freopen("input", "r", stdin);
#define fout freopen("output", "w", stdout);
#define wt(x) cerr << #x << ": " << x << " ";
#define whatis(x) {cerr << #x << ": " << x << endl;}
#define whatis2(x, y) {wt(x); wt(y); cerr << endl;}
#define whatis3(x, y, z) {wt(x); wt(y); wt(z); cerr << endl;}
#define whatis4(x, y, z, a) {wt(x); wt(y); wt(z); wt(a); cerr << endl;}
using namespace std;

typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1000000007; const ld PI = acos(-1.0);

template <typename T> inline T bigMod(T A,T B,T M = MOD){A %= M;T ret = 1;while(B){if(B & 1) ret = (ret * A) % M;A = (A * A) % M;B = B >> 1;}return ret;}
template <typename T> inline T invMod (T A,T M = MOD){return bigMod(A,M-2,M);}

const int N = 2999 + 10;
ld dp[N][N];

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

    
    int n;
    cin >> n;
    vector<ld> values(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> values[i];
    }

    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        dp[i][0] = dp[i-1][0] * (1 - values[i]);
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            dp[i][j] = values[i] * dp[i-1][j-1] + (1 - values[i]) * dp[i-1][j];
        }
    }

    /* for (int i = 0; i <= n; ++i) { */
    /*     for (int j = 0; j <= n; ++j) cout << dp[i][j] << '\t'; */
    /*     cout << endl; */
    /* } */

    ld ans = 0;
    int start = n/2 + 1;
    for (int i = start; i <= n; ++i) {
        ans += dp[n][i];
    }

    cout << setprecision(10) << ans << endl;



    return 0;
}


Measured memory_bytes: 141696
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) {
		FastScanner sc = new FastScanner(System.in);

		int N = sc.nextInt();
		int max4 = N /4;
		int max7 = N / 7;
		int total;
		int count = 0;

		for (int i4 = 0; i4 <= max4; i4++) {
			for (int i7 = 0; i7 <= max7; i7++) {
				total = i4*4 + i7*7;

				if (total == N) count++;
			}
		}

		if (count != 0) { System.out.println("Yes");} else { System.out.println("No");};
	}

	static class FastScanner {

		private BufferedReader reader = null;
	    private StringTokenizer tokenizer = null;

	    public FastScanner(InputStream in) {
	        reader = new BufferedReader(new InputStreamReader(in));
	        tokenizer = null;
	    }

	    public String next() {
	        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
	            try {
	                tokenizer = new StringTokenizer(reader.readLine());
	            } catch (IOException e) {
	                throw new RuntimeException(e);
	            }
	        }
	        return tokenizer.nextToken();
	    }

	    public String nextLine() {
	        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
	            try {
	                return reader.readLine();
	            } catch (IOException e) {
	                throw new RuntimeException(e);
	            }
	        }

	        return tokenizer.nextToken("\n");
	    }

	    public long nextLong() {
	        return Long.parseLong(next());
	    }

	    public int nextInt() {
	        return Integer.parseInt(next());
	    }

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

	    public int[] nextIntArray(int n) {
	        int[] a = new int[n];
	        for (int i = 0; i < n; i++)
	            a[i] = nextInt();
	        return a;
	    }

	    public long[] nextLongArray(int n) {
	        long[] a = new long[n];
	        for (int i = 0; i < n; i++)
	            a[i] = nextLong();
	        return a;
	    }

	}
}


Measured memory_bytes: 23124
#include<cstdio>
#include<algorithm>
typedef long long lint;
lint doz[23];
lint D;

lint dfs(int l,int r,lint d)
{
	if(l>=r)
	{
		if(d) return 0;
		return l==r?10ll:1ll;
	}
	if(d%10==0)
	{
		if(l==1) return dfs(l+1,r-1,d/10)*9;
		return dfs(l+1,r-1,d/10)*10;
	}
	lint di=d%10-10;
	lint de=d+di*(doz[r-l]-1ll);
	if(l==1) return dfs(l+1,r-1,(de>0?de:-de)/10)*(di+9);
	return dfs(l+1,r-1,(de>0?de:-de)/10)*(di+10);
}

int main()
{
	scanf("%lld",&D);
	doz[0]=1;for(int i=1;i<=18;i++) doz[i]=doz[i-1]*10ll;
	lint ans=0;
	for(int i=2;i<=18;i++) ans+=dfs(1,i,D);
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 128
n,m=map(int,input().split())
A=[input() for _ in range(n)]
B=[input() for _ in range(m)]

ans='No'
flag=False
for i in range(n-m+1):
    for j in range(n-m+1):
        C=[A[i+k][j:j+m] for k in range(m)]
        if B==C:
            ans='Yes'
        
print(ans)      

Measured memory_bytes: 3064
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>
#include <limits.h>

#define lli long long int
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define abs(a) ((a)<0?-(a):(a))

void solve(char **a,int i,int j){
	a[i][j] = '.';
	if(a[i+1][j] == '#'){
		solve(a,i+1,j);
	}else if(a[i][j+1] == '#'){
		solve(a,i,j+1);
	}
}


int main(void){
	int h,w;
	char **a;

	int i,j;

	scanf("%d%d",&h,&w);

	a = calloc(sizeof(char*),h+1);
	for(i=0;i<h;i++){
		a[i] = calloc(sizeof(char),w+1);
		scanf("%s",a[i]);
	}
	a[i] = calloc(sizeof(char),w+1);
	solve(a,0,0);
	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			if(a[i][j] == '#'){
				printf("Impossible\n");
				return 0;
			}
		}
	}

	printf("Possible\n");


    return 0;
}


Measured memory_bytes: 128
n,x = map(int,input().split())
a = list(map(int,input().split()))
cnt = 0
for i in range(n-1):
  if a[i]+a[i+1] > x:
    dif = min(a[i+1],a[i]+a[i+1]-x)
    a[i+1] -= dif
    cnt += dif
if a[0] > x:
  cnt += a[0]-x
print(cnt)

Measured memory_bytes: 14132
a , b , n = map(int , input().split())
l = 0
r = n
ans = 0
while (l < r) :
    mid = (l + r + 1) // 2
    if  (a * mid) // b - a * (mid // b) >= ans :
         ans =  (a * mid) // b - a * (mid // b)
         l = mid
    else :
        r = mid - 1
print((a * r) // b - a * (r // b))

Measured memory_bytes: 9136
import java.util.*;

class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt(),count=0;
        for(int ii=0;ii<n;ii++){
            int k = sc.nextInt();
            boolean flg = true;
            for(int i=2;i<=Math.sqrt(k);i++){
                if(k%i==0){flg=false;break;}
            }
            if(flg){
                count++;
            }
        }
        System.out.println(count);
    }
}


Measured memory_bytes: 42320
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 998244353
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**6)

n = int(input())
XD = [(-10**10,inf)]
for i in range(n):
  x,d = map(int,input().split())
  XD.append((x,d))
XD.sort()
visited = [0] * (n+1)
def dfs(node):
  visited[node] = 1
  res = 1
  i = node + 1
  while i < n+1:
    if XD[i][0] < XD[node][0] + XD[node][1]:
      if visited[i]:continue
      pro,i = dfs(i)
      res *= pro
      res %= mod
    else: break
  # print(node,res+1)
  return res + 1 , i
print((dfs(0)[0]-1)%mod)
# print(visited)
# print(XD)
# dfs(1)

Measured memory_bytes: 203964
import java.util.*;
class Main {
    static int[] a;
    static int n;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        a = new int[n];
        for(int i = 0; i<n; i++) a[i] = sc.nextInt();
        Arrays.sort(a);

        int b = a[n-1]/2;
        int pare = getNearB(b);
        System.out.println(a[n-1] +" " + pare);
    }
    public static int getNearB(int b) {
        int min = Integer.MAX_VALUE;
        int index = 0;
        for(int i = 0; i<n-1; i++) {
            if(min>= Math.abs(b-a[i])) {
                min = Math.abs(b-a[i]);
                index = i;
            }
        }
        return a[index];
    }
}

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

int mod = 1e9 + 7;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	int h, w;
	cin >> h >> w;
	string grid[h];
	for (int i = 0; i < h; i++) cin >> grid[i];
	
	long long dp[h][w];
	bool wl{};
	for (int i = 0; i < h; i++) {
		if (grid[i][0] == '#') wl = 1;
		dp[i][0] = !wl;
	}
	wl = 0;
	for (int i = 0; i < w; i++) {
		if (grid[0][i] == '#') wl = 1;
		dp[0][i] = !wl;
	}
	for (int i = 1; i < h; i++) {
		for (int j = 1; j < w; j++) {
			if (grid[i][j] == '#') dp[i][j] = 0;
			else dp[i][j] = (dp[i - 1][j] + dp[i][j - 1])%mod;
		}
	}
	cout << dp[h - 1][w - 1];
}

Measured memory_bytes: 12500
#include <cstdio>

int main()
{
    int n, x;
    scanf("%d %d", &n, &x);

    int min = 1000, sum = 0, temp;
    for(int i = 0; i < n; ++i)
    {
        scanf("%d", &temp);
        sum += temp;
        if(min > temp)
        {
            min = temp;
        }
    }

    printf("%d\n", n + (x - sum) / min);
    return 0;
}

Measured memory_bytes: 128
def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    import collections
    counter = collections.Counter(A)
    #print(counter)
    Q = int(input())
    BC = [list(map(int, input().split())) for _ in range(Q)]
    ans = sum(A)
    for b, c in BC:
        if b in counter:
            ans -= b*counter[b]
            ans += c*counter[b]
            if c not in counter:
                counter[c] = 0
            counter[c] += counter[b]
        counter[b] = 0
        #print(counter)
        print(ans)


if '__main__' == __name__:
    resolve()


Measured memory_bytes: 105756
#line 1 "/mnt/c/Users/leafc/dev/compro/lib/template.hpp"


#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>
#define MM << " " <<

using namespace std;

template <class T> void say(bool val, T yes = "Yes", T no = "No") { cout << (val ? yes : no) << "\n"; }

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

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


#line 2 "tmp.cpp"

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

  int n;
  cin >> n;
  ll cost[3][2];
  cin >> cost[0][0] >> cost[1][0] >> cost[2][0];
  cin >> cost[0][1] >> cost[1][1] >> cost[2][1];

  vl v1(n + 1, 0);

  REP(i, n + 1) {
    REP(j, 3) {
      if (cost[j][1] - cost[j][0] > 0 && i - cost[j][0] >= 0) {
        chmax(v1[i], v1[i - cost[j][0]] + cost[j][1]);
      }
    }
  }

  ll next = 0;
  REP(i, n + 1) { chmax(next, v1[i] + n - i); }

  vl v2(next + 1, 0LL);
  REP(i, next + 1) {
    REP(j, 3) {
      if (cost[j][0] - cost[j][1] > 0 && i - cost[j][1] >= 0) {
        chmax(v2[i], v2[i - cost[j][1]] + cost[j][0]);
      }
    }
  }

  ll ans = 0;
  REP(i, next + 1) { chmax(ans, v2[i] + next - i); }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 195584
#include<bits/stdc++.h>
typedef long long ll;
#define mod 1000000007
ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
ll fib[100];
std::vector<std::pair<ll,ll>>S[100];
int main(){
#ifdef XZZSB
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	fib[0]=fib[1]=1;for(int i=2;i<100;++i)fib[i]=fib[i-1]+fib[i-2];
	S[1].push_back({1,2});S[1].push_back({1,3});S[1].push_back({1,4});
	for(int i=1;i<99;++i){
		for(auto j:S[i]){
			ll x=j.second,y=j.first;
			y+=x;while(y<=fib[i+3]+fib[i])S[i+1].push_back({x,y}),y+=x;
		}
	}
	int Q=gi();
	while(Q--){
		ll X=gi(),Y=gi();if(X>Y)std::swap(X,Y);
		if(Y==1)puts("1 1");
		else{
			int p=1;
			while(X>=fib[p+1]&&Y>=fib[p+2])++p;
			if(p==1){printf("1 %d\n",X*Y%mod);continue;}
			int ans=0;
			for(auto pr:S[p-1]){
				ll x=pr.first,y=pr.second;
				if(y<=X)ans=(ans+(Y-x)/y)%mod;
				if(y<=Y)ans=(ans+(X-x)/y)%mod;
			}
			printf("%d %d\n",p,ans);
		}
	}
	return 0;
}


Measured memory_bytes: 4096
import java.util.*;

class Main {
    public static void main(String[] args) {
        new Solver().run();
    }   
}

class Solver {

    public void run() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();

        int[] x = new int[N];
        for (int i = 0; i < N; i++) {
            x[i] = sc.nextInt();
        }   

        int sum = 0;
        for (int i = 0; i < N; i++) {
            sum += 2 * Math.min(x[i], K - x[i]);
        }   

        System.out.println(sum);

        return;
    }   

}

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

int main(){
    int x;
    cin>>x;
    if(x>=30)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    
}

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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int main(){
  fastIO;
  string s, t;
  cin >> s >> t;
  for(int i = 0 ; i < s.size(); i ++ ){
    if(s[i] != t[i]){
      cout << "No\n";
      return 0;
    }

  }
  cout << "Yes\n";
  return 0;
}

Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;
void main_sub(void);
int main(int argc, char* argv[]) {
    cout << std::fixed << std::setprecision(10);
    main_sub();
    return 0;
}
// int を int64_t にする
// g++ に -DUSE_STRICT_INT をつけるか、
// 下のコメントアウトを外すと無効化
// #define USE_STRICT_INT
using i64 = int64_t;
#ifndef USE_STRICT_INT
#define int i64
#endif
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
constexpr int INF = (1 << 30);
constexpr i64 INFL = (1LL << 62);
constexpr i64 MOD = 1000000007;

void main_sub(void) {
    int n;
    cin >> n;
    int K = -1;

    for (int i = 1; i <= n; ++i) {
        if (i * (i + 1) / 2 == n) {
            K = i;
            break;
        }
    }
    if (K == -1) {
        puts("No");
    } else {
        puts("Yes");
        cout << K + 1 << endl;

        vector<vector<int> > res(K + 1, vector<int>());
        int sum = 1;
        for (int k = K; k >= 1; --k) {
            for (int i = 0; i < k; ++i) {
                res[K - k].push_back(sum + i);
                res[K - k + i + 1].push_back(sum + i);
            }
            sum += k;
        }

        rep(i, K + 1) {
            cout << res[i].size();
            rep(j, res[i].size()) { cout << " " << res[i][j]; }
            cout << endl;
        }
    }

    return;
}

Measured memory_bytes: 3200
#include <stdio.h>

int main(){

int h, w;
int x, y;
char c;

while (1){
scanf("%d %d", &h, &w);

if (h == 0 && w == 0) break;

for  (y = 0; y < h; y++ ){
        for (x = 0; x < w; x++){
                if (y == 0 || y == h - 1 || x == 0 || x == w - 1 ) c = '#';
                else c = '.';

                printf("%c", c);}
                printf("\n");
                        }
                printf("\n");
}
return 0;
}

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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair

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

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


#define INF 1'000'000'000

int main() {
    i64 N, K, S; cin >> N >> K >> S;
    vector<i64> A(N);
    REP(i, N) {
        if (i >= K) {
            i64 s1 = min((i64)INF, S + 1);
            if (s1 != S) A[i] = s1;
            else A[i] = S - 1;
        } else A[i] = S;
    }

    REP(i, N) cout << A[i] << " ";
    cout << endl;

    return 0;
}

Measured memory_bytes: 2176
#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);

int n;
int pp[100010],ss[100010], a[100010];

int main() {
	cin >> n;
	for (int i =0;i<n;i++) cin >> a[i];
	pp[0] = abs(a[0]);
	for (int i =1;i<n;i++) {
		pp[i] = pp[i-1] + abs(a[i-1] - a[i]);
	}
	for (int i = n-1; i>=0;i--) ss[i] = ss[i+1] + abs(a[i+1] - a[i]);
	
	for (int i =0;i<n;i++) {
		cout << pp[i-1] + ss[i+1] + abs(a[i+1] - a[i-1]) << "\n";
	}
	
}


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

int main(void){
	int N;
	cin >> N;
	long long A[N];
	long long sum = 0;
	bool flag = false;
	int cnt=0;
	long long minus = 1e9+7;
	for(int i=0;i<N;i++){
		cin >> A[i];
		sum += abs(A[i]);
		if(A[i]==0)flag=true;
		minus = min(minus,abs(A[i]));
		if(A[i]<0)cnt++;
	}
	if(flag==true)cout << sum << endl;
	else if(cnt%2){
		cout << sum - 2*minus << endl;
	}else{
		cout << sum << endl;
	}
}

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

int main()
{
    int N,c,d,a;
    vector<int> vec(100);

    cin >> N;
    d=0;
    a=0;

    for(int i=0;i<N;i++){
        cin >> vec.at(i);
    }

for(int a=0;a<(N-1);a++){
    for(int i=1;i<N;i++){
           c=vec.at(a)*vec.at(a+i);
           d=d+c;
        }
}
    

    cout << d <<endl;
}

Measured memory_bytes: 256
#include<iostream>

int main (void)
{
	int a, b;
	std::cin >> a;
	std::cin >> b;

	if (a > b)
		std::cout << "a > b" << '\n';
	else if (a < b)
		std::cout << "a < b" << '\n';
	else
		std::cout << "a == b" << '\n';

}

Measured memory_bytes: 1128
n=int(input())
xu=[]
total=0
for i in range(n):
    xu.append([x for x in input().split()])

a=380000.0
for i in range(n):
    if xu[i][1]=="JPY":
        total+=float(xu[i][0])
    else:
        total+=float(xu[i][0])*a
print(total)


Measured memory_bytes: 3060
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
namespace mp = boost::multiprecision;

int main(){
	// int n=1;
	// vector<int> a(n);

 	string s;
	cin >> s;
	int n = s.length();

	mp::cpp_int ret = 0;
	char pre = s[0];
	mp::cpp_int pre_num = 0;
	mp::cpp_int temp = 0;
	mp::cpp_int count = 1;

	bool flag = (s[0] == '>') ? true : false;

	for (int i = 0; i<n; i++) {
		// cout << temp << ",";
		ret += temp;
		// cout << "ret" << ret << endl;
		if (s[i] == pre) {
			if (s[i] == '<') {
				temp++;
			} else {
				temp--;
			}
			count++;
		} else {
			if (s[i] == '<') {
				// cout << "pre_num" << pre_num << endl;
				// cout << "temp" << temp << endl;
				// cout << "count" << count << endl;
				if (pre_num > -1 * temp) {
					ret += temp * -1 * (count - 1);
				} else {
					if (flag) {
						ret += temp * -1 * (count - 1) + (-1 * temp - pre_num);
						flag = false;
					} else {
						ret += temp * -1 * (count - 1) + (-1 * temp - pre_num + 1);
					}
				} 
				temp = 1;
			} else {
				pre_num = temp;
				temp = 0;
			}
			count = 2;
		}
		pre = s[i];
	}
	// cout << "pre_num" << pre_num << endl;
	// cout << "temp" << temp << endl;
	// cout << "count" << count << endl;
	ret += temp;
	if (s[n-1] == '>') {
		if (pre_num > -1 * temp) {
			ret += temp * -1 * (count - 1);
		} else {
			if (flag) {
				ret += temp * -1 * (count - 1) + (-1 * temp - pre_num);
				flag = false;
			} else {
				ret += temp * -1 * (count - 1) + (-1 * temp - pre_num + 1);
			}
		}
	}

	cout << ret;

	return 0;
}

Measured memory_bytes: 1148
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std;
int main()
{
    int n,k;
    cin>>n>>k;
    if(k>=n) k=n-1;
    int h[n],minC[n],x[k];
    for(int i=0;i<n;i++) cin>>h[i];
    minC[0]=0;
    for(int i=1;i<k;i++) minC[i]=abs(h[i]-h[0]);
    for(int i=k;i<n;i++)
    {
        for(int j=1;j<=k;j++) x[j-1]=abs(h[i]-h[i-j])+minC[i-j];
        minC[i]= *min_element(x,x+k);
    }
    cout<<minC[n-1]<<endl;
    return 0;
}

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

int main() {
    int N;
    cin >> N;
    vector<int> H(N);
    for (int i = 0; i < N; i++) {
        cin >> H.at(i);
    }
    string ans = "Yes";
    for (int j = 0; j < N - 1; j++) {
        if ((H.at(j) <= H.at(j+1)) || (H.at(j) <= H.at(j+1) - 1) ) {
            if ((H.at(j) <= H.at(j+1) - 1)) {
                H.at(j+1) = H.at(j+1) - 1;
            }
            continue;
        } else {
            ans = "No";
            break;
        }
    }
    cout << ans << endl;

}


Measured memory_bytes: 640
#include <iostream>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <algorithm>
#include <map>

using namespace std;
typedef long long ll;
const ll N_MAX = 100100;
vector<ll> arr(N_MAX);
ll Q;


void Eratosthenes(){
	for(int i = 2; i < N_MAX; i++){
		arr[i] = 1;
	}
	for(int i = 2; i < sqrt(N_MAX); i++){
		if(arr[i]){
			for(int j = 0; i * (j + 2) < N_MAX; j++){
				arr[i *(j + 2)] = 0;
			}
		}
	}
}


int main() {
    cin >> Q;
    vector<ll> res(N_MAX);
    Eratosthenes();
    for(int i=0;i<N_MAX;i++){
        if(arr[i]==1 && arr[(i+1)/2]==1) res[i]=1;
    }
    for(int i=1;i<N_MAX;i++){
        res[i]+=res[i-1];
    }
    vector<ll> L(Q),R(Q);
    for(int i=0;i<Q;i++){
        cin >> L[i] >> R[i];
    }
    for(int i=0;i<Q;i++){
        cout << res[R[i]]-res[L[i]-1] << endl;
    }
}

Measured memory_bytes: 3712
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int maxn = 200005;
int n;
ll ans;
int head[maxn], nxt[maxn << 1], tail[maxn << 1], ecnt;

void addedge(int u, int v) {
	nxt[++ecnt] = head[u];
	head[u] = ecnt;
	tail[ecnt] = v;
}

void dfs(int u, int p) {
	for (int e = head[u]; e; e = nxt[e]) {
		int v = tail[e];
		if (v != p) {
			int mn = min(v, u), mx = max(v, u);
			ans -= (ll)mn * (n - mx + 1);
			dfs(v, u);
		}
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n - 1; i++) {
		int u, v; scanf("%d%d", &u, &v);
		addedge(u, v); addedge(v, u);
	}
	for (int i = 1; i <= n; i++) ans += (ll)i * (n - i + 1); // contribution for nodes
	dfs(1, 0); // contribution for edges
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 16996
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
#define pll pair<long long, long long>
set<pll>D[19][19];
int n, w[19];
void Put(int b, int e, pll a) {
	D[b][e].insert(a);
	auto it = D[b][e].find(a);
	auto it2 = it;
	it2++;
	if (it2 != D[b][e].end() && it2->second >= a.second) {
		D[b][e].erase(it);
		return;
	}
	while (it != D[b][e].begin()) {
		it2 = it; it2--;
		if (it2->second <= a.second) {
			D[b][e].erase(it2);
		}
		else break;
	}
}
int main() {
	int i, j, k;
	//srand(1879);
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf("%d", &w[i]);
		//w[i] = (rand() % 1000) * 1000000 + (rand() % 1000) * 1000 + rand() % 1000;
		w[i] = -w[i];
	}
	for (i = 1; i < n; i++) {
		D[i][i + 1].insert({ w[i],w[i + 1] });
	}
	for (i = 2; i < n; i++) {
		for (j = 1; j <= n - i; j++) {
			int b = j, e = j + i;
			for (k = b + 1; k < e; k++) {
				for (auto &t1 : D[b][k]) {
					for (auto &t2 : D[k][e]) {
						long long f = t1.second + t2.first - w[k];
						Put(b, e, { t1.first + f, t2.second + f });
					}
				}
			}
		}
	}
	long long res = -1e18;
	for (auto &t : D[1][n])res = max(res, t.first + t.second);
	printf("%lld\n", -res);
}

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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll inf = 1e9 + 5;
typedef pair<int, bool> pib;

int main() {
    ll n,w; cin >> n >> w;
    vector<ll> dp (w+1);
    //dp state is max at a certain weight from 0 to weight n
    for (ll i = 0; i < n; i++){
        ll cv,cw; cin >> cw >> cv;
        for (ll weightused = w; weightused >= cw; weightused--){
            dp[weightused] = max(dp[weightused], dp[weightused-cw] + cv);
        }
    }
    cout << *max_element(dp.begin(), dp.end());
}



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

using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
typedef long long ll;
#define INF 1e9





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

    vector<int> a(n), b(n);
    rep(i,n) cin >> a[i];
    rep(i,n) cin >> b[i];
    vector<int> amari(n);
    ll husoku = 0;
    int cnt = 0;
    rep(i,n) {
        if(b[i] > a[i]){
            husoku += (b[i] - a[i]);
            cnt++;
        }
    }
    int ans = 0;
    rep(i,n) {
        if(a[i] > b[i]){
            amari[i] = (a[i] - b[i]);
            
            
        }
    }
    if(husoku == 0){
        cout << 0 << endl;
        return 0;
    }
    
    sort(amari.begin(), amari.end());
    for(int i=n-1; i>=0; i--){
        husoku -= amari[i];
        ans++;
        if(husoku <= 0){
            break;
        }
    }
    if(husoku>0){
        cout << -1 << endl;
        return 0;
    }
    
    cout << ans + cnt << endl;
}


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

int main(){
	int r,g,b;
	cin >> r >> g >> b;
	if((g*10+b)%4 == 0) cout << "YES" << endl;
	else cout << "NO" << endl;
}

Measured memory_bytes: 256
# 1,2,3
# 01
# 10
# 11

# 両隣のXORと一致->両隣と自分をXORすると0になる
# 連続した3つのXORが0になる
# a,b,c,dでaとdは同じになる

# 円環になるには、
# a,b,c,a,b,cというセットになり、
# 且つa,b,cのXORが0であればよい

# もしくは全部0

# もしくはa,a,0,a,a,0

n=int(input())
a=list(map(int,input().split()))
dis=set(a)
if a[0]==0 and len(dis)==1:
  print("Yes")
  exit(0)
if len(dis)==3:
  xor=0
  cur=0
  for c in dis:
    xor^=c
    cnt=a.count(c)
    if cur==0:
      cur=cnt
    else:
      if cnt!=cur:
        print("No")
        exit(0)
  if xor==0:
    print("Yes")
    exit(0)
if len(dis)==2:
  if a.count(0)==n//3 and n%3==0:
    print("Yes")
    exit(0)
print("No")

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

#define DUMP(x) cerr << #x << "=" << x << endl
#define DUMP2(x, y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<")"<< endl
#define BINARY(x) static_cast<bitset<16> >(x)

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

#define in_range(x, y, w, h) (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))
#define ALL(a) (a).begin(),(a).end()

typedef long long ll;
const int INF   = 1e9;
const ll  INFLL = 1e18;
typedef pair<int, int> PII;
int dx[4]={0, -1, 1, 0}, dy[4]={-1, 0, 0, 1};

const int MAX_N = 310;
const ll MOD = 1e9 + 7;
ll dp[MAX_N][MAX_N][MAX_N];
map<int, vector<pair<int, int>>> constrains;
int N, M;

int main()
{
    ios::sync_with_stdio(false);

    cin >> N >> M;
    rep(i, M) {
        int L, R, X;
        cin >> L >> R >> X;
        constrains[R].emplace_back(L, X);
    }
    ll ans = 0;
    dp[0][0][0] = 1;

    rep(r, N+1) rep(g, N+1) rep(b, N+1) {
        int k = max({r, g, b});
        bool ok = true;

        if (constrains[k].size()) {
            for (auto p : constrains[k]) {
                int cl = p.first, cr = k, cx = p.second;
                int y = 0;
                y += (cl <= r && r <= cr);
                y += (cl <= g && g <= cr);
                y += (cl <= b && b <= cr);
                if (y != cx) {
                    dp[r][g][b] = 0;
                    ok = false;
                    break;
                }
            }
        }

        if (ok) {
            (dp[k+1][g][b] += dp[r][g][b]) %= MOD;
            (dp[r][k+1][b] += dp[r][g][b]) %= MOD;
            (dp[r][g][k+1] += dp[r][g][b]) %= MOD;
        }

        if (k == N) {
            (ans += dp[r][g][b]) %= MOD;
#ifdef DEBUG
            DUMP(ans);
#endif
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 227712
def check(num):
    n = str(num)
    for i in range(len(n)):
        if n[i] == '3': return True
    return False

n = int(input())
for i in range(1, n + 1):
    if i % 3 == 0: print(' ' + str(i), end = '')
    elif check(i):
        print(' ' + str(i), end = '')
print()



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

#define ll long long

void swap (int *x, int *y) {
  int temp;

  temp = *x;
  *x = *y;
  *y = temp;

  return;
}


int gcd(int a, int b){
  int c;

  while (b > 0){
    c = a % b;
    a = b;
    b = c;
  }

  return a;
}

int upll(const void*a, const void*b){
  return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;
}

int downll(const void*a, const void*b){
  return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;
}

void sortup(ll*a,int n){
  qsort(a,n,sizeof(ll),upll);
}

void sortdown(ll*a,int n){
  qsort(a,n,sizeof(ll),downll);
}

long int modpow(long int a,long int n,long int mod){
  long int ans=1;
  while(n>0){
    if(n & 1){
      ans=ans*a%mod;
    }
    a=a*a%mod;
    n/=2;
  }
  return ans;
}

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

int max(int a,int b){
  if(a<b){
    return b;
  }
  else{
    return a;
  }
}

int min(int a,int b){
  if(a<b){
    return a;
  }
  else{
    return b;
  }
}

void chmax(int *a,int b){
  if(*a < b){
    *a = b;
  }

  return;
}

void chmin(int *a,int b){
  if(*a > b){
    *a =b;
  }

  return;
}


/****************************************\
| Thank you for viewing my code:)        |
| Written by RedSpica a.k.a. RanseMirage |
| Twitter:@asakaakasaka                  | 
\****************************************/

int main(void){
  int MOD=1e9+7;

  long int n;
  scanf("%ld",&n);

  long int ans=0;

  long int kai[2000000];
  long int rekai[2000000];
  
  kai[0]=1;
  kai[1]=1;
  for(int i=2;i<2000000;i++){
    kai[i]=kai[i-1]*i;
    kai[i]%=MOD;
  }

  
  rekai[0]=1;
  rekai[1]=1;
  for(int i=2;i<2000000;i++){
    rekai[i]=rekai[i-1]*modinv(i,MOD);
    rekai[i]%=MOD;
  }

  for(long int i=2;i<=n;i++){
    long int a=i;//0or9の個数
    long int b=n-i;//それ以外の個数

    long int now=1;
    now=modpow(2,a,MOD)-2+MOD;//aのところの組合せ
    now%=MOD;

    now*=modpow(8,b,MOD);//b
    now%=MOD;

    now*=kai[n];
    now%=MOD;

    now*=rekai[a];
    now%=MOD;

    now*=rekai[b];
    now%=MOD;

    ans+=now;
    ans%=MOD;
  }

  printf("%ld\n",ans);

  return 0;
}

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


def solve(N: int, K: int, a: "List[int]", b: "List[int]"):
    ab = sorted([[a[i],b[i]] for i in range(N)], key=lambda x:x[0])
    nt = -1
    for ia,ib in ab:
        nt += ib
        if(nt >= K-1):
            print(ia)
            exit()
        
    print(ab[-1][0])


        


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    a = [int()] * (N)  # type: "List[int]" 
    b = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, K, a, b)

if __name__ == '__main__':
    main()


Measured memory_bytes: 23720
/*{{{*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
#include<limits.h>
#include<assert.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define RS(X) scanf("%s", (X))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(LL &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const LL &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
#ifdef HOME
 #define DEBUG(...) {printf("# ");printf(__VA_ARGS__);puts("");}
#else
 #define DEBUG(...)
#endif
int MOD = 1e9+7;
void ADD(LL& x,LL v){x=(x+v)%MOD;if(x<0)x+=MOD;}
/*}}}*/
const int SIZE = 1e6+10;
int d[SIZE];
int main(){
    int n; R(n);
    FOR(i,1,n){
        int x;
        R(x);
        d[x]++;
    }
    sort(d,d+n+1,greater<int>());
    int pos=0,div=0,all=n;
    FOR(i,1,n){
        if(d[pos]==0){
            W(0);
            continue;
        }
        div++;
        while(d[pos]>all/div){
            all-=d[pos++];
            div--;
        }
        W(all/div);
    }
    return 0;
}


Measured memory_bytes: 2048
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <sstream>

#define endl "\n"
using namespace std;
using ll = long long;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define REP(i, n) for(int i = 0; i < n; i++)
using Graph = vector<vector<int>>;

int main(){
    int n;
    cin>>n;
    vector<ll> a(n);
    ll sum = 0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        sum += a[i];
    }
    ll ans = 0, half = 0;
    for(int i=0;i<n;i++){
        if(half <= sum/2 && sum/2 + 1 <= half + a[i]){
            ans = sum-half-half;
            if(i != 0) ans = min(ans, half+a[i] - (sum-(half+a[i])));
            break;
        }
        else half += a[i];
    }

    cout<<ans<<endl;
}

Measured memory_bytes: 4824
#include<bits/stdc++.h>
using namespace std;
string s;
int main(){
	cin>>s;
	for(int i=1;i<s.size();i++){
		if(s[i]==s[i-1]){
			cout<<"Bad";
			return 0;
		}
	}
	cout<<"Good";
	return 0;
} 

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n)for(int i=0;i<(int)(n);i++)
#define PI 3.141592653589793
//vector < vector<int>>a(0, vector<int>(0));二次元配列宣言


int main()
{
	int n;
	cin >> n;
	if (n / 100 == n % 10)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;

} 

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

int main(){
    int n;
    cin >> n;
    cout << "ABC" << setfill('0') << setw(3) << n << endl;
    return 0;
}

Measured memory_bytes: 256