akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>
#define rep(i, n)   for(int i = 0; i < (n); i++)
using namespace std;

int h, w;
vector<vector<char> >s;

vector<vector<int> >cost;
int bfs(int starty, int startx){
    if(s[starty][startx] == '#')    return 0;
    int dx[] = {0, 1, 0, -1};
    int dy[] = {1, 0, -1, 0};
    queue<pair<int, int> >que;
    que.push(make_pair(starty, startx));
    cost[starty][startx] = 0;
    int M = 0;
    while(!que.empty()){
        pair<int, int> p = que.front();
        que.pop();
        //somethig
        rep(i, 4){
            M = max(M, cost[p.first][p.second]);
            int ny = p.first + dy[i];
            int nx = p.second + dx[i];
            if(nx < 0 || ny < 0 || nx >= w || ny >= h)  continue;
            if(s[ny][nx] == '#')    continue;
            if(cost[ny][nx] != -1)  continue;
            cost[ny][nx] = cost[p.first][p.second] + 1;
            que.push(make_pair(ny, nx));
        }
    }
    return M;
}

int main(){
    cin >> h >> w;
    s = vector<vector<char> >(h, vector<char>(w));
    rep(i, h)   rep(j, w)   cin >> s[i][j];
    cost = vector<vector<int> >(h, vector<int>(w, -1));
    int ans = 0;
    rep(i, h)   rep(j, w){
        ans = max(ans, bfs(i, j));
        cost = vector<vector<int> >(h, vector<int>(w, -1));
    }
    cout << ans << endl;
}


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

int BubbleSort(char C[36][2], int N) {
  int i, j;
  char m,s;
  for (i = 0; i < N; i++) {
    for (j = N -1; j > 0; j--) {
      if (C[j][1] < C[j-1][1]) {
        s = C[j][0]; m = C[j][1];
        C[j][0] = C[j-1][0]; C[j][1] = C[j-1][1];
        C[j-1][0] = s; C[j-1][1] = m;
      }
    }
  }
  return 0;
}

int SelectionSort(char C[36][2], int N) {
  int i, j, minj;
  char m,s;
  for (i = 0; i < N; i++) {
    minj = i;
    for (j = i; j < N; j++) {
      if (C[j][1] < C[minj][1]) {
        minj = j;
      }
    }
    s = C[i][0]; m = C[i][1];
    C[i][0] = C[minj][0]; C[i][1] = C[minj][1];
    C[minj][0] = s; C[minj][1] = m;
  }
  return 0;
}

int comp(char C[36][2], char p[36][2], int N) {
  int i;
  int ret = 0;
  for (i = 0; i < N; i++) {
    if (C[i][0] != p[i][0] || C[i][1] != p[i][1]) {
      ret = 1;  i = N;
    }
  }
  return ret;
}

int main() {
  int i, j, N, pp, ret;
  char C[36][2];
  char C2[36][2];
  char p[36][2];
  char in[20];
  char c0 = '0';
  cin >> N;
  for (i = 0; i < N; i++) {
    cin >> in;
    C[i][0] = C2[i][0] = in[0];
    C[i][1] = C2[i][1] = in[1];
  }
  pp = 0;
  for (i = 1; i < 10; i++) {
    for (j = 0; j < N; j++) {
      if (C[j][1] == c0 + i) {
        p[pp][0] = C[j][0]; p[pp][1] = C[j][1];
        pp++;
      }
    }
  }
  BubbleSort(C, N);
  for (i = 0; i < N; i++) {
    if (i != 0)     cout << " ";
    cout << C[i][0] << C[i][1];
  }
  cout << endl;
  if (comp(C, p, N) != 0) {
    cout << "Not stable" << endl;
  } else {
    cout << "Stable" << endl;
  }
  SelectionSort(C2, N);
  for (i = 0; i < N; i++) {
    if (i != 0)     cout << " ";
    cout << C2[i][0] << C2[i][1];
  }
  cout << endl;
  if (comp(C2, p, N) != 0) {
    cout << "Not stable" << endl;
  } else {
    cout << "Stable" << endl;
  }
  return 0;
}


Measured memory_bytes: 3128
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int A, B;
  cin >> A >> B;

  if (B % A == 0) {
    cout << A + B << endl;
  } else {
    cout << B - A << endl;
  }

  return 0;
}

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

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

	vector<long long int> divisor;
	for (int i = 1; i <= sqrt(n); i++) {
		if (n % i == 0) {
			divisor.push_back(i);
			divisor.push_back(n/i);
		}
	}
	long long int min = 1e12;
	for (int i = 0; i < divisor.size(); i+=2) {
		if (divisor[i] - 1 + divisor[i+1] - 1 < min) {
			min = divisor[i] - 1 + divisor[i+1] - 1;
		}
	}
	cout << min << endl;
	return 0;
}

Measured memory_bytes: 384
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		System.out.println(Math.min(Math.min(sc.nextInt(), sc.nextInt()), sc.nextInt()) + Math.min(sc.nextInt(), sc.nextInt()) - 50);
	}
}

Measured memory_bytes: 26172
#include<bits/stdc++.h>
using namespace std;
long long M = pow(10, 9) + 7;
long long power(long long a, long long b) {
	if (b == 0) return 1;
	if (b % 2) return (a * power(a, b - 1)) % M;
	long long k = power(a, b / 2);
	return (k * k) % M;
}
const int Max=1e6+2;
int Power[Max];
int Fact[Max];
int invF[Max];
void help(){
	Power[0]=0;
	long long p=1;
	long long r=1;
	Fact[0]=1;
	invF[0]=1;
	long long q=1;
	for(long long i=1;i<Max;i++){
		p=(p*9)%M;
		r=(r*8)%M;
		Power[i]=(p-r+M)%M;
		q=(q*i)%M;
		Fact[i]=q;
		invF[i]=power(q,M-2);
	}
}
int solve(){
	long long n,k;
	cin>>n;
	if(n==1) return 0;
	help();
	long long ans=0,x,y,a,b,c;
	a=Fact[n];
	for(int i=1;i<n;i++){
		b=invF[i],c=invF[n-i];
		x=(((b*c)%M)*a)%M;
		int k=n-i;
		y=Power[k];
		ans= (ans+(x*y)%M)%M;
	}
	return ans;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout<<solve();

}

Measured memory_bytes: 15344
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define REVETSE(c) reverse((c).begin(),(c).end())
#define SUM(c) accumulate((c).begin(),(c).end(),0)
#define ALL(a)  (a).begin(),(a).end()
// int gcd(int a,int b){return b?gcd(b,a%b):a;}
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
template<class T> T maxt(T x,T y) {
    if (x>y) return x;
    else return y;
}
template<class T> T mint(T x,T y) {
    if (x>y) return y;
    else return x;
}
//sort(v.rbegin(), v.rend(), [](auto& x, auto& y){return x[1] < y[1];});
//cout << fixed << setprecision(10) << ans << defaultfloat << endl;
typedef long long ll;
typedef vector<int> Vi;
typedef vector<ll> Vl;
typedef vector<double> Vd;
typedef vector<string> Vs;

//小数出力
double print_double(double d){printf("%.10f", d);}

long long m = 1e9+7, mod = 1e9+7;
//逆元　a/b の modをとるとき -> a*modinv(b)%mod
long long modinv(long long a, long long m = 1e9+7) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}

//約数列挙
vector< int64_t > divisor(int64_t n) {
  vector< int64_t > ret;
  for(int64_t i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}








int main() {
  int X,Y,ix,iy;
  cin >> X >> Y;
  if ((X+Y)%3!=0) {
    cout << 0 << endl;
    return 0;
  }
  if  ((X+Y)/3 > mint(X,Y)) {
    cout << 0 << endl;
    return 0;
  }
  ix = mint(X,Y) - (X+Y)/3;
  iy = (X+Y)/3;

  if (X+Y==0) {
    cout << 0 << endl;
    return 0;
  }
  ll ans = 1;
  rep(i,ix) {
    ans = ans*(iy-i)%mod;
  }
  rep(i,ix) {
    ans = ans*modinv(i+1)%mod;
  }
  cout << ans;
}

Measured memory_bytes: 384
N=int(input())
T,A=map(int,input().split())
H=[-1000]+list(map(int,input().split()))


M=10**10
X=0
for i in range(1,N+1):
    B=abs(1000*(T-A)-6*H[i])
    if B<=M:
        M=B
        X=i
print(X)
    


Measured memory_bytes: 62692
#include <cstdio>
#include <algorithm>
#define SIZE 33554432
char Key[128];
int Hash;
char* c;
#define HASH(A) c = A; Hash = 1; while(*c){ Hash <<= 2; Hash += Key[*c]; ++c;}
using namespace std;
int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    Key['A'] = 0;
    Key['C'] = 1;
    Key['G'] = 2;
    Key['T'] = 3;
    bool* dic = new bool[SIZE];
    fill(dic, dic + SIZE, false);
    int n;
    std::scanf("%d\n", &n);
    char str[21];
    for (int i = 0; i < n; ++i) {
        fgets(str, 21, stdin);
        if (str[0] == 'i') {
            HASH(str + 7)
                dic[Hash] = true;
        }
        else {
            HASH(str + 5)
                puts((dic[Hash] ? "yes" : "no"));
        }
    }
    return 0;
}

Measured memory_bytes: 35372
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
#include<map>
#include<queue>
#include<set>
#include<bitset>
#include<stdio.h>
#include<deque>
#include<iomanip>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
typedef long long ll;

int main()
{
    ll n, m;
    cin >> n >> m;
    priority_queue<ll> q;
    rep(i, n){
        ll a;
        cin >> a;
        q.push(a);
    }
    rep(i, m){
        ll a = q.top();
        q.pop();
        q.push(a/2);
    }
    ll ans = 0;
    rep(i, n){
        ans += q.top();
        q.pop();
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1400
#!/usr/bin/env python
# -*- coding: utf-8 -*-

def solve():
    a, b = map(int, input().split())
    ans = "x"
    if a + b == 15:
        ans = "+"
    if a * b == 15:
        ans = "*"
    print(ans)

if __name__=="__main__":
    solve()


Measured memory_bytes: 2940
n,x=gets.split.map &:to_i
l=gets.split.map &:to_i
sum,cnt=0,1
(0...n).each do |i|
  sum += l[i]
  if sum == x
    cnt += 1
    break
  elsif sum >= x
    break
  end
  cnt +=1
end
puts cnt

Measured memory_bytes: 1788
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>

using namespace std;

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define REPO(i, n) for(int i = 1;i <= n;i++)
#define ll long long
#define INF 1999999999
#define MINF -1999999999
#define INF64 1999999999999999999
#define ALL(n) n.begin(),n.end()

string s;
ll dp[11000][110][2],N;
int main() {
	dp[0][0][0] = 1;
	cin >> s >> N;
	REP(i, s.size()) {
		REP(l, N) {
			REP(j, 2) {
				int a = j ? 9 : s[i] - '0';
				REP(k, a + 1) {
					dp[i + 1][(l + k) % N][j or k < a] += dp[i][l][j];
					dp[i + 1][(l + k) % N][j or k < a] %= 1000000007;

				}
			}
		}
	}
	ll ans = -1;
	REP(i, 2) ans += dp[s.size()][0][i];
	cout << (ans + 1000000007) % 1000000007 << endl;
}

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

int main()
{
    int n,f=1;
    cin>>n;
    int x[n];
    for(int i=0;i<n;i++)cin>>x[i];
    for(int i=0;i<n;i++)
    {
        if(x[i]==f)f++;

    }
    if(f==1)cout<<"-1"<<endl;
    else cout<<n-f+1<<endl;

    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
using namespace std;
int n,m;
int memo[100001];
int a[21];
int main()
{
	for(int i = 0;i<100000;i++)
	{
		memo[i]=99999;
	}
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		cin>>a[i];
	}
	memo[0]=0;
	for(int i = 0;i<n;i++)
	{
		for(int l = 0;l< m;l++)
		{
			memo[i+a[l]]=min(memo[i+a[l]],memo[i]+1);
		}
	}
	cout<<memo[n]<<endl;
	
	
	return 0;
}

Measured memory_bytes: 1552
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    N, M = NMI()
    keys = {}
    for i in range(M):
        a, b = NMI()
        C = NLI()
        case = 0
        for c in C:
            case += 2**(c-1)
        keys[i+1] = (a, case)

    dp = [[10**10] * (2**N) for _ in range(M+1)]
    dp[0][0] = 0

    for key in range(0, M):
        for case in range(2**N):
            if dp[key][case] == 10**10:
                continue
            next_case = case | keys[key+1][1]
            dp[key+1][next_case] = min(dp[key][case] + keys[key+1][0], dp[key+1][next_case])
            dp[key+1][case] = min(dp[key][case], dp[key+1][case])
    ans = dp[M][2**N-1]
    print(ans if ans < 10**10 else -1)






if __name__ == "__main__":
    main()

Measured memory_bytes: 42308
#include<bits/stdc++.h>
using namespace std; 
#define ll long long int
#define pb push_back
#define mp make_pair
#define pll pair<ll,ll>
#define INF LLONG_MAX
#define PI acos(-1)
const ll MOD = 1e9 + 7;
#define x first
#define y second
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(c,a,b) for(ll c=a;c<b;c++)
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define min_heap priority_queue<pll,vector<pll>,greater<pll> >
ll dx4[]={-1,1,0,0};
ll dy4[]={0,0,-1,1};
ll dx8[]={-1,-1,-1,0,1,1,1,0};
ll dy8[]={-1,0,1,1,1,0,-1,-1};
bool isvalid(ll x,ll y,ll n,ll m)
{
	return (x>=0 and y>=0 and x<n and y<m);
}
ll isprime[1000];
vector<ll> prime;
void sievetoprime(ll n)
{
	mem(isprime,true);
	for(ll p=2;p*p<=n;p++)
	{
		if(isprime[p]==true)
		{
			for(ll i=p*p;i<=n;i+=p)
				isprime[i]=false;
		}
	}
}
ll lcm(ll a,ll b)
{
	return (a/__gcd(a,b))*b;
}
bool cmp(pair<string,ll> a,pair<string,ll> b)
{
	if(a.first<b.first)
		return 1;
	else if(a.x==b.x)
	{
		return a.y<b.y;
	}
	return 0;
}
void solve()
{
	ll n,k;
	cin>>k>>n;
	ll a[n];
	rep(i,0,n)
	{
		cin>>a[i];
	}
	vector<ll> v;
	for(ll i=1;i<n;i++)
		v.pb(a[i]-a[i-1]);
	v.pb(k-a[n-1]+a[0]);
	sort(all(v));
	ll ans=accumulate(v.begin(),v.end()-1,0);
	cout<<ans<<endl;
}	

int main()
{
	IOS
	ll t;
	t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
}

Measured memory_bytes: 3956
#include <bits/stdc++.h>
using namespace std;
#define fo(i,a,b) for(int i=(a);i<(b);i++)
#define MOD 1000000007
#define MP make_pair
#define PB push_back
typedef long long ll;

int N;
ll dp[2200200], cum, tot;

int main () {
        scanf("%d", &N);
        dp[0] = 1ll;
        fo(i, 1, N+1) {
                if (i-3 >= 0) {
                        cum += dp[i-3];
                        if (cum >= MOD) cum -= MOD;
                }
                dp[i] = cum + dp[i-1];
                if (dp[i] >= MOD) dp[i] -= MOD;
        }
        //fo(i, 0, N+1) printf("dp %d %lld\n", i, dp[i]);

        //if all ones:
        tot = 1ll;
        //now force self to have non-1 before infinity
        fo(i, 0, N) {
                //can put shit here before final
                //can put 2... N
                //with values 3... N+1
                //and at least has to get to N
                //some number ... then go infinity
                ll a = dp[i] * (N-1) % MOD;
                if (i < N-1) a = a * N % MOD;
                //printf("%d: %lld %lld\n", i, dp[i], a);
                tot = (tot + a) % MOD;
        }

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



Measured memory_bytes: 8448
#include<bits/stdc++.h>
long long a[100001],b[100000];
using namespace std;
int main()
{
	long long n,ma,ac,ba=0;
	cin>>n;
	for(int t=0;t<=n;t++)
	{
		cin>>a[t];
	}
	for(int t=0;t<n;t++)
	{
		cin>>b[t];
	}
	for(int t=0;t<n;t++)
	{
		ma=a[t];
		ac=b[t];
		ba=ba+min(ac,ma);
		ac=ac-min(ac,ma);
		ba=ba+min(ac,a[t+1]);
		a[t+1]=a[t+1]-min(ac,a[t+1]);
	}
	cout<<ba;
	return 0;
} 

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

#define ld long double
#define ll long long
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define MP make_pair
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
ll INF = 1e18;
void chmin(ll &a,ll b){if(a>b)a=b;}
void chmax(ll &a,ll b){if(a<b)a=b;}
void pmod(ll &a,ll b){a=(a+b)%MOD;}
void qmod(ll &a,ll b){a=(a*b)%MOD;}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
void ans(bool x,ll y,ll z){if(x)cout<<y<<endl;else cout<<z<<endl;}
void ans(bool x,string y,string z){if(x)cout<<y<<endl;else cout<<z<<endl;}   
ll gcd(ll x,ll y){ll r;while((r=x%y)!=0){x=y;y=r;}return y;}

int main(){
  ll i,j,o;
  ll res=0,res1=INF,res2=-INF,buf=0,buf1=0,buf2=0,buf3=0,buf4=0,sum=0;
  ll l,r;
  bool judge = true;
  ll a,b,c;cin>>a>>b>>c;
  set<ll>s;
  s.insert(a);
  s.insert(b);
  s.insert(c);
  cout<<s.size()<<endl;

  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  int i;
  int info[110000];
  int number[110000];
  for(i=0;i<n;i++){
    cin >> info[i];
    number[info[i]]=i+1;
  }
  for(i=0;i<n;i++){
    cout << number[i+1] << " " ;
  }
  return(0);
}

Measured memory_bytes: 1664
//#include <tourist>
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<ll, ll> p;
const int INF = 1e9;
const ll LINF = ll(1e18);
const int MOD = 1000000007;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#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 debug(v)          \
    cout << #v << ":";    \
    for (auto x : v)      \
    {                     \
        cout << x << ' '; \
    }                     \
    cout << endl;
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;
}
//cout<<fixed<<setprecision(15);有効数字15桁
//-std=c++14
//g++ yarudake.cpp -std=c++17 -I .
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,q;
    cin>>n>>q;
    dsu d(n);
    rep(i,q){
        int t;
        cin>>t;
        int a,b;
        cin>>a>>b;
        if(t==1){
            if(d.same(a,b))cout<<1<<"\n";
            else cout<<0<<"\n";
        }
        else{
            d.merge(a,b);
        }
    }
}

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

int main(){
    int a[4];
    for(int i=0;i<4;i++){
        cin >> a[i];
    }
    sort(a,a+4);
    if(a[0]==1&&a[1]==4&&a[2]==7&&a[3]==9) cout << "YES" << endl;
    else cout << "NO" << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
  int H, W;
  
  while(1){
    int i, j;
    
    scanf("%d %d",&H, &W);
    //ループから抜け出す条件
    if(H == 0 && W == 0)
      break; 
    
    for(i=1;i <= H;i++){
      for(j=1;j <= W;j++){
	if(i == 1 || i == H){
	  printf("#");
	}
        else if(j == 1 || j == W){
          printf("#");
	}
        else{
          printf(".");
	}
      }
      printf("\n");
    }
    printf("\n");
  }
  return 0;
}

Measured memory_bytes: 572
#include <iostream>
#include <iomanip>
#include <sstream>
#include <stdio.h>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <math.h>
#include <utility>
#include <string>
#include <ctype.h>
#include <cstring>
#include <cstdio>
#include <sstream>
using namespace std;

#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define INF 114514810
#define ll long long
//#define scanf scanf_s

int main()
{
	vector<int> v;
	int a;
	while (cin >> a) 
	{
		if (a != 0) v.push_back(a);
		else
		{
			cout << v.back() << endl;
			v.pop_back();
		}

	}
	return 0;
}

Measured memory_bytes: 1208
def countBombs(y,x):
	count = 0
	for n in range(y-1,y+2):
		for m in range(x-1,x+2):
			# print(n)
			# print(m)
			if n < 1 or m < 0\
			 or n > int(inputsMassNum[0]) or m > int(inputsMassNum[1])-1:
				pass
			elif inputsBombs[n][m] == "#":
				count += 1

	return count
	

inputsBombs = [[]] 

#3*3想定
if __name__ == '__main__':
	input1 = input()
	inputsMassNum = input1.split()#3 3

	for i in range(0,int(inputsMassNum[0])):#0~3(3回)
		# print(i)
		input2 = input()#
		inputsBombs.append(list(input2)) #[0][]は空
		#  [   ] 
		#	###
		#	#.#
		#	###

		#inputBombs,「1」要素に追加
		# print(inputsBombs[i+1])
			
	for y in range(1,int(inputsMassNum[0])+1):#0~3
		for x in range(0,int(inputsMassNum[1])):
			# print(inputsBombs[y][x])
			if inputsBombs[y][x] == ".":#
				tmp = countBombs(y,x)
				inputsBombs[y][x] = tmp


	inputsBombs.pop(0)
	# for i in range(0,int(inputsMassNum[0])):
	# 	print(inputsBombs)

	for i in range(0,int(inputsMassNum[0])):
		for j in range(0,int(inputsMassNum[1])):
			print(inputsBombs[i][j],end = "")
		print("")


Measured memory_bytes: 3444
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define ss second
#define ff first
#define INF 30000000000001
#define ll_max 9000000000000000001
#define mod 1000000007
#define PI 3.14159265358979323846L
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
typedef vector<pair<ll,ll> > vll;
typedef vector<pair<int,int> > vii ;
typedef pair<ll,ll> pll;
const ll N = 100001;
const ll M = 1;

void update(ll BIT[], ll n, ll x, ll i)
{
    for(; i <= n; i += (i) & (-i)) BIT[i] += x;
}

ll query(ll BIT[], ll l)
{
    ll sum1 = 0;
    for(; l; l = l & (l - 1)) sum1 += BIT[l];
    return sum1;
}

int main()
{
    fast;
    int _ = 1;
    //cin >> _;
    while(_--)
    {
        ll n, m = 0, x = 0, y = 0, ans = 0, r = 0;
        cin >> n >> m >> x;
        if(m > n) swap(n, m);
        while(y < x)
        {
            ans++;
            y += n;
        }
        cout << ans << "\n";
    }
    return 0;
}


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

using namespace std;

int main(){
    int n,d;
    int res = 0;
    cin >> n >> d;
    vector<int> v[n];
    for (int i=0; i<n;i++){
        for (int j = 0; j < d; j++){
            int t;
            cin >> t;
            v[i].push_back(t);
        }
    }
    for (int i = 0; i < n; i++){
        for (int j = i+1; j < n; j++){
            double a = 0;
            for (int y = 0; y < d; y++){
                a += (v[i][y] - v[j][y])*(v[i][y] - v[j][y]);
            }
            a = sqrt(a);
            double f;
            double f1 = modf(a, &f);
            if (a == f) res++;
        }
    }
    cout << res;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <list>
#include <set>
#include <stack>
#include <cctype>
#include <cmath>

using namespace std;

/* typedef */
typedef long long ll;

/* constant */
const int INF = 1 << 30;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;

/* global variables */

/* function */

/* main */
int main(){

    int q; cin >> q;
    int op, x;
    string l, r;
    string key;
    map<string, int> M;
    using iterator  = decltype(M)::iterator;

    for (int i = 0; i < q; i++) {
        cin >> op >> key;
        switch(op) {
            case 0:
                cin >> x;
                // insert(key, x) :
                // Insert an element formed by a pair of key and x to M
                M[key] = x;
                break;
            case 1:
                // get(key): Print the value with the specified key
                // if M[key] is not exist
                // => M[key] = 0 and return 0
                // exist => return M[key]
                if (M.count(key))
                    cout << M[key] << '\n';
                else
                    cout << 0 << '\n';
                break;
            case 2:
                // delete(key): Delete the element with the specified key
                M.erase(key);
                break;
            case 3:
                cin >> r;
                l = key;
                iterator head = M.lower_bound(l);
                iterator tail = M.upper_bound(r);
                for ( ; head != tail; head++)
                    cout << (*head).first << ' ' << (*head).second << '\n';
                break;
        }
    }

}



Measured memory_bytes: 27832
#include <string>
#include <iostream>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <map>
#include <utility>
#include <set>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	int N, x;
	cin >> N >> x;

	if(x == 1 || x == 2*N-1)
	{
		cout << "No" << endl;
		return 0;
	}

	cout << "Yes" << endl;
	if(N == 2)
	{
		cout << "1\n2\n3" << endl;
		return 0;
	}
	vector<int> res(2*N-1);

	if(x == 2)
	{
		res[(2*N-1)/2 - 1] = x+1;
		res[(2*N-1)/2] = x;
		res[(2*N-1)/2 + 1] = x-1;
		res[(2*N-1)/2 + 2] = x+2;
	}
	else
	{
		res[(2*N-1)/2 - 1] = x-1;
		res[(2*N-1)/2] = x;
		res[(2*N-1)/2 + 1] = x+1;
		res[(2*N-1)/2 + 2] = x-2;
	}
	

	int val = 1;
	for(int i = 0; i < (int)res.size(); ++i)
	{
		while(i >= (2*N-1)/2 - 1 && i <= (2*N-1)/2 + 2)
			++i;
		while(x == 2 && val >= x-1 && val <= x+2)
			++val;
		while(x != 2 && val >= x-2 && val <= x+1)
			++val;
		res[i] = val++;
	}
	for(int i = 0; i < (int)res.size(); ++i)
		cout << res[i] << endl;
	return 0;
}

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

long long n, x, m;
bool zero = 0;
vector<long long> v;

int main() {
  cin >> n >> x >> m;
  vector<vector<long long>> memo, sum;
  memo.assign(60, vector<long long>(m, 0));
  sum.assign(60, vector<long long>(m, 0));
  for (int i = 0; i < m; ++i) memo[0][i] = (long long)i * i % m;
  for (int i = 0; i < m; ++i) sum[0][i] = i;
  for (int i = 1; i < 60; ++i)
    for (int j = 0; j < m; ++j) memo[i][j] = memo[i - 1][memo[i - 1][j]];
  for (int i = 1; i < 60; ++i)
    for (int j = 0; j < m; ++j) {
      long long mid = memo[i - 1][j];
      sum[i][j] = sum[i - 1][j] + sum[i - 1][mid];
    }
  long long res = 0;
  for (int i = 0; i < 60; ++i)
    if (n >> i & 1) {
      res += sum[i][x];
      x = memo[i][x];
    }
  cout << res << endl;
  return 0;
}

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

public class Main {
	static PrintWriter out;
	static StringBuilder sb;
	static long mod = 998244353;

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		out = new PrintWriter(System.out);
		int n = sc.nextInt();
		int k = sc.nextInt();
		char[] a = sc.nextLine().toCharArray();
		long ans = 0;
		if (k == 2 || k == 5) {
			for (int i = 0; i < n; i++) {
				int x = Integer.parseInt("" + a[i]);
				if (x % k == 0)
					ans += (long) (i + 1);
			}
		} else {
			HashMap<Integer, Long> h = new HashMap<>();
			int sum = 0;
			h.put(0, 1l);
			int te=1;
			for (int i = n-1; i >=0; i--) {
				int x = Integer.parseInt("" + a[i]);
				sum += x*te;
				te=te*10;
				te%=k;
				sum %= k;
                ans+=h.getOrDefault(sum, 0l);
                h.put(sum, 1l+h.getOrDefault(sum, 0l));
			}
		}
		out.print(ans);
		out.flush();
	}

	static class pair implements Comparable<pair> {
		int to;
		int number;

		pair(int t, int n) {
			number = n;
			to = t;
		}

		public String toString() {
			return to + " " + number;
		}

		@Override
		public int compareTo(pair o) {
			return to - o.to;
		}

	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}

		public Scanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

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

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

		public char nextChar() throws IOException {
			return next().charAt(0);
		}

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

		public boolean ready() throws IOException {
			return br.ready();
		}

		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
}

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

using namespace std;
const int mod = 1000000007;

int main(){
    string S;
    cin >> S;
    // cout << S << endl;
    bool ans = true;
    for (int i = 0; i < S.size(); i++){
        if (S.at(i) == 'L'){
            ans = false;
        }
        i++;
    }
    for (int i = 1; i < S.size(); i++){
        if (S.at(i) == 'R'){
            ans = false;
        }
        i++;
    }
    if (ans == true){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <limits.h>
#include <algorithm>
using namespace std;

int main()
{
    int k,n,x;
    cin>>n>>k;
    int a[n];
    long long sum;
    int max=INT_MIN;
    
    for(int i=0;i<n;i++)
        cin>>a[i];
        
    sort(a,a+n);
    
    sum=0;
    for(int i=0;i<n-k;i++){
        sum+=a[i];
    }
    
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 1024
/*  -*- coding: utf-8 -*-
 *
 * c.cc: C: Bridge
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 50;

/* typedef */

typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef stack<int> si;

/* global variables */

vi nbrs[MAX_N];

/* subroutines */

void bcc_visit(const vi *nbrs, int v, int u,
	       vpii& brdg, vvi& tecomp,
	       si& roots, si& S, vb& inS, vi& num, int& time) {
  num[v] = ++time;
  S.push(v); inS[v] = true;
  roots.push(v);

  const vi& nbrv = nbrs[v];
  for (vi::const_iterator vit = nbrv.begin(); vit != nbrv.end(); vit++) {
    const int& w = *vit;
    if (num[w] == 0)
      bcc_visit(nbrs, w, v, brdg, tecomp, roots, S, inS, num, time);
    else if (u != w && inS[w])
      while (num[roots.top()] > num[w]) roots.pop();
  }

  if (v == roots.top()) {
    brdg.push_back(pii(u, v));
    tecomp.push_back(vi());
    for (;;) {
      int w = S.top(); S.pop(); inS[w] = false;
      tecomp.back().push_back(w);
      if (v == w) break;
    }
    roots.pop();
  }
}

void calc_bcc(const int n, const vi *nbrs,
	      vpii& brdg, vvi& tecomp) {
  vi num(n);
  vb inS(n);
  si roots, S;
  int time = 0;

  for (int u = 0; u < n; u++)
    if (num[u] == 0) {
      bcc_visit(nbrs, u, n, brdg, tecomp, roots, S, inS, num, time);
      brdg.pop_back();
    }
}

/* main */

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

  for (int i = 0; i < m; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--, b--;
    nbrs[a].push_back(b);
    nbrs[b].push_back(a);
  }

  vpii brdg;
  vvi tecomp;

  calc_bcc(n, nbrs, brdg, tecomp);
  printf("%lu\n", brdg.size());
  return 0;
}


Measured memory_bytes: 256
def main():
    input()
    mod = 10**9 + 7
    arr = sorted(map(int, input().split()))
    arr.reverse()

    sm = arr[0] + arr[1]
    ans = arr[0] * arr[1] % mod

    for x in range(2, len(arr)):
        ans += sm * arr[x]
        sm += arr[x]

    print(ans % mod)


if __name__ == '__main__':
    main()

Measured memory_bytes: 31520
#include <iostream>
#include <cstdio>
using namespace std;
struct st{int x[4];};
int h, w, k, a[505][505];
int b[250005], c[250005], d[250005],e[250005];
int main() {
	int i, j;
	scanf("%d%d", &h, &w);
	for(i=1; i<=h; i++) for(j=1; j<=w; j++) scanf("%d", &a[i][j]);
	for(i=1; i<=h; i++) for(j=1; j<=w; j++) if(a[i][j]%2) {
		if(j!=w) a[i][j+1]++, b[k]=i, c[k]=j, d[k]=i, e[k]=j+1, k++;
		else if(i!=h) a[i+1][j]++, b[k]=i, c[k]=j, d[k]=i+1, e[k]=j, k++;
	}
	printf("%d\n", k);
	for(i=0; i<k; i++) printf("%d %d %d %d\n", b[i], c[i], d[i], e[i]);
	return 0;
}

Measured memory_bytes: 6016
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
 
int main(){
  int d[5];
  scanf("%d %d %d %d %d", &d[0], &d[1], &d[2], &d[3], &d[4]);
  
  vector< pair<int, int> > vc(5);
  for(int i=0; i<5; i++) {
    int d_last = ((d[i] + 9) % 10) * -1; // １の位を取る、0を一番大きく1を一番小さくしたい
    vc[i] = make_pair(d_last, i);
  }
  sort(vc.begin(), vc.end());
  
  // 大きい順に取れば良い
  int sum_time = 0;
  for(int i=0; i<4; i++) {
    sum_time += ((d[vc[i].second] + 9) / 10 * 10);
  }
  sum_time += d[vc[4].second];
  
  printf("%d", sum_time);
  return 0;
}

Measured memory_bytes: 256
def resolve():
    N = int(input())
    L = [0]*N
    R = [0] * N
    for i in range(N):
        l, r = map(int, input().split())
        L[i] = l
        R[i] = r

    L.sort()
    R.sort()
    ans = 0
    if N%2 == 1:
        mid_L = L[N//2]
        mid_R = R[N // 2]
        ans = mid_R - mid_L +1
    else:
        mid_L = L[N // 2-1] + L[N // 2]
        mid_R = R[N // 2-1] + R[N // 2]
        ans = mid_R - mid_L + 1

    print(ans)

if __name__ == "__main__":
    resolve()


Measured memory_bytes: 25300
#ifdef MY_LOCAL
#define MY_NAMESPACE(ns) namespace ns {
#define MY_NAMESPACE_    }
#define MY_DEBUG(s)      s
#else
#define MY_NAMESPACE(ns) 
#define MY_NAMESPACE_    
#define MY_DEBUG(s)      
#endif

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <vector>

using namespace std;

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

#define EPS (1e-7)
#define IINF ((int)1e9)


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

	int n;
	cin >> n;
	vector<ll> num_divs(n + 1, 2);  // init with 2 because 1 and n are divisors
	num_divs[1] = 1;
	for (int k = 2; k * 2 <= n; k++)
	{
		for (int j = k * 2; j <= n; j += k)
		{
			num_divs[j]++;
		}
	}
	ll res = 0;
	for (int k = 1; k <= n; k++)
	{
		res += k * num_divs[k];
	}
	cout << res << "\n";
	return 0;
}
MY_NAMESPACE_

Measured memory_bytes: 81324
# 2019/08/18
# AtCoder Beginner Contest 138 - C

# Input
n = int(input())
v = list(map(int,input().split()))

# Sort
v.sort()
#v.reverse()

# Sum
sav_v = v[0]
for i in range(1, n):
    sav_v = (sav_v + v[i]) / 2

ans = sav_v

# Output
print(ans)


Measured memory_bytes: 2940
# -*- coding utf-8 -*-
N = int(input())
A = list(map(int, input().split()))

s = sum(A)
x = s - 2 * sum(A[1::2])
print(x, end='')

for i in range(N - 1):
    x = 2 * A[i] - x
    print(' ' + str(x), end='')
print()


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

using ll = long long;
using P = pair<int, int>;

// 4近傍、8近傍
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

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

  cout << min(c, b / a) << endl;
  return 0;
}


Measured memory_bytes: 256
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    q = I()
    m = 10**5+1
    f = [0]*m
    s = 0
    for i in a:
        s += i
        f[i] += 1
    for _ in range(q):
        b,c = LI()
        ns = s+(c-b)*f[b]
        f[c] += f[b]
        f[b] = 0
        print(ns)
        s = ns
    return

#Solve
if __name__ == "__main__":
    solve()


Measured memory_bytes: 82212
import java.util.*;

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

        int n = sc.nextInt();

        List<double[]> list = new ArrayList<>();

        for (int i=0; i<n; i++){
            double a = sc.nextDouble();
            double b = sc.nextDouble();
            double[] t = new double[2];
            t[0] = a;
            t[1] = b;
            list.add(t);
        }

        double ans = 0;

        for (int i=0; i<n; i++){
            for (int j=i+1; j<n; j++){
                double[] tmp1 = list.get(i);
                double[] tmp2 = list.get(j);
                double tmp = Math.sqrt(Math.pow(tmp2[0]-tmp1[0],2)+Math.pow(tmp2[1]-tmp1[1],2));
                ans += tmp;
            }
        }

        ans *= 2*Math.pow(n, -1);

        System.out.println(ans);
    }
}

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

int main(){
    string s;cin>>s;vector<int> list(58);int n=0;
    for(int i=0;i<s.size();i++){
        list.at(s.at(i)-'A')++;
    }
    for(int i=32;i<58;i++) n+=list.at(i);
    if(s.at(0)=='A'&&list.at(2)==1&&n==s.size()-2&&s.at(1)!='C'&&s.at(s.size()-1)!='C') cout<<"AC"<<endl;
    else cout<<"WA"<<endl;
}

Measured memory_bytes: 256
'''
隣接リストを用いた実装
O(ElogV) ：次に探す頂点をプライオリティーキューを用いて探索
V: 頂点数
G[i] = [(j, c_ij) for j in (iに隣接する頂点）]
'''
import heapq

def Dijkstra(G, start):
    d = [float('inf')] * V
    d[start] = 0
    q =[]
    heapq.heappush(q, (0, start))
    while len(q) > 0:
        dist, v  = heapq.heappop(q)
        if d[v] < dist:
            continue
        for j, cost in G[v]:
            if d[j] > d[v] + cost:
                d[j] = d[v] + cost
                heapq.heappush(q, (d[j], j))
    return d

V, E, s, t = map(int, input().split())
Yen = [[] for _ in range(V)]
Snuke = [[] for _ in range(V)]
for i in range(E):
    ui, vi, ai, bi = map(int, input().split())
    Yen[ui - 1].append((vi - 1, ai))
    Yen[vi - 1].append((ui - 1, ai))
    Snuke[ui - 1].append((vi - 1, bi))
    Snuke[vi - 1].append((ui - 1, bi))

Yen_min = Dijkstra(Yen, s - 1)
Snuke_min = Dijkstra(Snuke, t - 1)
dist = [(Yen_min[i] + Snuke_min[i]) for i in range(V)]
ans = [float('inf') for i in range(V)]
ans[V - 1] = dist[V - 1]
for i in range(V - 2, -1, -1):
    ans[i] = min(dist[i], ans[i + 1] )
for i in range(V):
    print(10 ** 15 - ans[i])

Measured memory_bytes: 88984
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 3010

ll power(ll k, ll n, int M){
  ll res = 1;
  while(n > 0) {
    if (n & 1) res = res * k % M;
    k = k * k % M;
    n /= 2;
  }
  return res;
}

/* ラグランジュ補間 */

// y[i] = f(x[i]) mod P
// 0 <= x[i], y[i] < P
// f = sum(res[i] * x^i)
vector<int> lagrangeInterpolation(const vector<int> &x, const vector<int> &y, int P) {
  int N = x.size();
  vector<ll> Q(N+1);
  vector<int> res(N);

  Q[0] = 1;
  for (int i=0; i<N; i++) {
    for (int j=i; j>=0; j--) {
      Q[j+1] = (Q[j+1] - Q[j] + P) % P;
      Q[j] = Q[j] * x[i] % P;
    }
  }

  for (int i=0; i<N; i++) {
    ll ainv = power(x[i], P-2, P), c = 1;

    for (int j=0; j<N; j++)
      if (i != j) c = c * (x[j] - x[i] + P) % P;

    ll prev = Q[0], p = (ll)y[i] * power(c, P-2, P) % P;
    for (int j=0; j<N; j++) {
      ll v = x[i] ? prev * ainv % P : P - Q[j+1]; //: Q[j+1] * inv(-1) % P;
      res[j] = (v * p + res[j]) % P;
      prev = (Q[j+1] + v) % P;
    }
  }

  return res;
}

int main() {
  int P;

  cin >> P;

  vector<int> y(P), x(P);

  for(int i=0; i<P; i++) {
    cin >> y[i];
    x[i] = i;
  }

  auto res = lagrangeInterpolation(x, y, P);

  for (int i=0; i<P; i++) {
    printf("%d%c", res[i], " \n"[i==P-1]);
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define SORT(a) sort(a.begin(), a.end())
#define RSORT(a) sort(a.rbegin(), a.rend())
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, start, end) for (int i = start; i < end; i++)
#define ALL(a) a.begin(), a.end()
#define MOD(a) a %= 1'000'000'007
using ll = long long;
using namespace std;
const int INF32       = 1'050'000'000;
const long long INF64 = 4'000'000'000'000'000'000;
const int MOD7        = 1'000'000'007;
const int MOD9        = 1'000'000'009;
template <class T> inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
void print() { std::cout << '\n'; }
void vprint() { std::cout << '\n'; }
template <class H, class... T> void print(H &&head, T &&... args) {
    std::cout << head;
    sizeof...(args) == 0 ? std::cout << "" : std::cout << ' ';
    print(std::forward<T>(args)...);
}
template <class T> void print(std::vector<T> &v) {
    for (int i = 0; i < v.size(); i++) {
        std::cout << v[i];
        i == v.size() - 1 ? std::cout << '\n' : std::cout << ' ';
    }
}
template <class T> void print(std::vector<std::vector<T>> &v) {
    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < v[i].size(); j++) {
            std::cout << v[i][j];
            j == v[i].size() - 1 ? std::cout << '\n' : std::cout << ' ';
        }
    }
}
template <class H, class... T> void vprint(H &&head, T &&... args) {
    std::cout << head;
    sizeof...(args) == 0 ? std::cout << "" : std::cout << '\n';
    vprint(std::forward<T>(args)...);
}
template <class T> void vprint(std::vector<T> &v) {
    for (auto &&i : v) {
        std::cout << i << '\n';
    }
}
template <class T> void mprint(std::vector<std::vector<T>> &v) {
    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < v[i].size(); j++) {
            std::cout << v[i][j];
            j == v[i].size() - 1 ? std::cout << '\n' : std::cout << "";
        }
    }
}

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

    int H, W;
    cin >> H >> W;
    vector<vector<char>> a(H, vector<char>(W));
    vector<vector<char>> ans(H, vector<char>(W, '0'));
    REP(i, H) REP(j, W) cin >> a[i][j];

    vector<int> dx = {-1, -1, -1, 0, 0, 1, 1, 1};
    vector<int> dy = {-1, 0, 1, -1, 1, -1, 0, 1};
    auto exist     = [](int H, int W, int nx, int ny) -> bool {
        if (nx < 0 || W <= nx || ny < 0 || H <= ny)
            return false;
        else
            return true;
    };

    REP(y, H) {
        REP(x, W) {
            if (a[y][x] == '#') {
                ans[y][x] = '#';
                REP(i, 8) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    if (exist(H, W, nx, ny) && a[ny][nx] != '#') {
                        ans[ny][nx]++;
                    }
                }
            }
        }
    }
    mprint(ans);

    return 0;
}

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

// Binary Indexed Tree (Fenwick Tree)
// https://youtu.be/lyHk98daDJo?t=7960
template<typename T>
struct BIT {
  int n;
  vector<T> d;
  BIT(int n=0):n(n),d(n+1) {}
  void add(int i, T x=1) {
    for (i++; i <= n; i += i&-i) {
      d[i] += x;
    }
  }
  T sum(int i) {
    T x = 0;
    for (i++; i; i -= i&-i) {
      x += d[i];
    }
    return x;
  }
  T sum(int l, int r) {
    return sum(r-1) - sum(l-1);
  }
};

int main() {
	int q_num;
	cin >> q_num;
	vector<tuple<int, int, int>> q;
	ll fmin;
	int lmin;
	vector<int> tor;
	rep(i, q_num) {
		int t;
		cin >> t;
		if (t == 1) {
			int a, b;
			cin >> a >> b;
			if (i == 0) {
				fmin = b;
				lmin = a;
			}
			else q.emplace_back(t, a, b);
			tor.push_back(a);
		}
		else q.emplace_back(t, 0, 0);
	}
	tor.push_back(-1001001001);
	sort(tor.begin(), tor.end());
	tor.erase(unique(tor.begin(), tor.end()), tor.end());
	map<int, int> toc;
	for(int i = 0; i < tor.size(); i++) toc[tor[i]] = i;

	BIT<int> bt(tor.size());
	bt.add(0, -1);
	bt.add(toc[lmin], 2);
	for(auto p: q) {
		int t, a, b;
		tie(t, a, b) = p;
		if (t == 2) {
			cout << lmin << ' ' <<  fmin << endl;
			continue;
		}
		bt.add(0, -1);
		bt.add(toc[a], 2);
		int nl;
		{
			int l = -1, r = tor.size();
			while(r - l > 1) {
				int c = (l + r) / 2;
				if (bt.sum(c) >= 0) r = c;
				else l = c;
			}
			nl = tor[r];
		}
		if (nl < lmin) {
			fmin += lmin - nl;
		}
		lmin = nl;
		fmin += abs<ll>(a - lmin) + b;
	}
}


Measured memory_bytes: 10416
#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[101][101];
int s[10001][10001];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	}
for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]=='#')
            {
                s[i-1][j-1]++;
                s[i-1][j]++;
                s[i-1][j+1]++;
                s[i][j-1]++;
                s[i][j+1]++;
                s[i+1][j-1]++;
                s[i+1][j]++;
                s[i+1][j+1]++;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]=='#')
                cout<<"#";
            else
                printf("%d",s[i][j]);
        }
        cout<<endl;
    }   
	return 0;}

Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <iomanip>
#include <bitset>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);++i)
#define rep(i,a,b) for(int i=a;i<(b);++i)
template<class T> inline bool chmin(T &a, T b){ if(a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){ if(a < b) { a = b; return true;} return false;}
using ll = long long;
constexpr ll INF = 1LL << 60;
constexpr int MOD = 998244353;

ll n, m, p[100010];
bool ac[100010];
ll pen[100010];

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

  REP(i, m) {
    ll a;
    string s;
    cin >> a >> s;
    --a;
    if (s[0] == 'A') {
      ac[a] = true;
    } else {
      if (!ac[a]) ++pen[a];
    }
  }
  ll acc = 0;
  ll pe = 0;
  REP(i, n) if(ac[i]){
    ++acc;
    pe += pen[i];
  }

  cout << acc << " " << pe;
  return 0;
}

Measured memory_bytes: 1152