akhauriyash/Code-Regression huggingface dataset:
// Test for study
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
 
template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

const ll INF = 1e17;
ll N, M, L, Q;
ll fuel[305][305];
ll dist[305][305];
ll s[105000], t[105000];
ll A[100000], B[100000], C[100000];

int main() {
  cin >> N >> M >> L;
  for (int i = 1; i <= M; i++)
  {
    cin >> A[i] >> B[i] >> C[i];
  }
  cin >> Q;
  for (int i = 1; i <= Q; i++)
  {
    cin >> s[i] >> t[i];
  }
  
  for (int i = 1; i <= N; i++)
  {
    for (int j = 1; j <= N; j++)
    {
      fuel[i][j] = INF;
      dist[i][j] = INF;
    }
    fuel[i][i] = 0;
    dist[i][i] = 0;
  }
  
  for (int i = 1; i <= M; i++)
  {
    chmin(fuel[A[i]][B[i]], C[i]);
    chmin(fuel[B[i]][A[i]], C[i]);
  }
  
  for (int i = 1; i <= N; i++)
  {
    for (int j = 1; j <= N; j++)
    {
      for (int k = 1; k <= N; k++)
      {
        chmin(fuel[j][k], fuel[j][i] + fuel[i][k]);
      }
    }
  }
  
  for (int i = 1; i <= N; i++)
  {
    for (int j = 1; j <= N; j++)
    {
      if (i == j)
      {
        continue;
      }
      if (fuel[i][j] <= L)
      {
        dist[i][j] = 1LL;
      }
    }
  }
  
  for (int i = 1; i <= N; i++)
  {
    for (int j = 1; j <= N; j++)
    {
      for (int k = 1; k <= N; k++)
      {
        chmin(dist[j][k], dist[j][i] + dist[i][k]);
      }
    }
  }
  
  for (int i = 1; i <= Q; i++)
  {
    if (dist[s[i]][t[i]] < INF)
    {
      cout << dist[s[i]][t[i]] - 1 << endl;
    }
    else
    {
      cout << -1 << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 4864
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define REPL(i,m,n) for(ll i=(ll)(m); i<(ll)(n); i++)
#define repl(i,n) REPL(i,0,n)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
int main() {
  int N;
  string S, T;
  cin >> N >> S >> T;
  rep(i, N) {
    bool ok = true;
    rep(j, N-i) {
      if(S[i+j] != T[j]) {
	ok = false;
	break;
      }
    }
    if(ok) {
      cout << i+N << endl;
      return 0;
    }
  }
  cout << 2*N << endl;
  return 0;
}


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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef long long ll;

ll dp[3100][3100]; // dp[i][j] => [i, j) 半開区間

int main() {
    int N;
    cin >> N;
    vector<int> a(N);
    rep(i, N) cin >> a[i];

    // 初期条件
    rep(i, N) dp[i][i] = 0;

    for (int len = 1; len <= N; ++len) {
        for (int i = 0; i + len <= N; ++i) {
            int j = i + len;

            // 先手番
            if ((N - len) % 2 == 0)
                dp[i][j] = max(dp[i + 1][j] + a[i], dp[i][j - 1] + a[j - 1]);

                // 後手番
            else
                dp[i][j] = min(dp[i + 1][j] - a[i], dp[i][j - 1] - a[j - 1]);
        }
    }

    cout << dp[0][N] << endl;
}

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

int main(){
  int N;
  int maxn;
  cin >> N;
  cin >> maxn;
  
  int a[N-1];
  for (int i=1;i<N;i++){
    cin >> a[i];
    if(maxn-a[i]>1){
      cout << "No";
      return 0;
    }
    maxn = max(a[i],maxn); 
  }
  cout << "Yes" << endl;
}

Measured memory_bytes: 640
#include<iostream>
using namespace std;
int main() {
	char X, Y;
	cin >> X >> Y;
	if ((int)X > (int)Y) {
		cout << ">" << endl;
	}else if ((int)X < (int)Y) {
		cout << "<" << endl;
	}
	else {
		cout << "=" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll          long long int
#define pb          push_back
#define pll         pair<ll,ll>
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mod         998244353
#define mode        1000000007
#define inf         1000000000000000000LL
#define vl          vector<ll>
#define F           first
#define S           second
#define db          long double
#define sz(x)       (ll)x.size()
#define fix(n)      cout<<fixed<<setprecision(n)
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define all(x)      x.begin(),x.end()
#define mset(x)     memset(x,0,sizeof x)
#define pi          3.14159265358979323

const int N = 3e5+5;
ll n,a[N];

void solve()
{
       cin>>n;
       rep(i,1,3*n+1) cin>>a[i];
       sort(a+1,a+3*n+1);
       ll ans=0;
       ll i=3*n-1;
       rep(j,0,n)
       {
              ans+=a[i-2*j];
       }
       cout<<ans;
}


int main()
{
    speed_up
    ll T=1;
    //cin>>T;
    while(T--)
        solve();
    return 0;
}


Measured memory_bytes: 2560
# -*- coding: utf-8 -*-

sx, sy, tx, ty = map(int, input().split())

h = ty - sy
w = tx - sx

ans = "U"*h
ans += "R"*w
ans += "D"*h
ans += "L"*(w+1)
ans += "U"*(h+1)
ans += "R"*(w+1)
ans += "D"
ans += "R"
ans += "D"*(h+1)
ans += "L"*(w+1)
ans += "U"

print(ans)

Measured memory_bytes: 3064
A = list(input())
B = list(input())
C = list(input())
i,j,k = 0,0,0
now = "a"

while 1:
    if now == "a":
        if i < len(A):
            now = A[i]
            i += 1
        else:
            break
    if now == "b":
        if j < len(B):
            now = B[j]
            j += 1
        else:
            break
    if now == "c":
        if k < len(C):
            now = C[k]
            k += 1
        else:
            break

print(now.upper())


Measured memory_bytes: 3064
a = int(input())
c = {}
c['AC'] = c['WA'] = c['TLE'] = c['RE'] = (int)(0)
for _ in range(a):
  c[input()]+=1
print('AC x ', end = '')
print(c['AC'])

print('WA x ', end = '')
print(c['WA'])

print('TLE x ', end = '')
print(c['TLE'])

print('RE x ', end = '')
print(c['RE'])


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

//#define INF 1000000000;
#define MOD 1000000007;
#define LIMIT 1000000000000000000;
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define int long long
typedef pair<int, int> P;

struct Setup {
    Setup() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} SETUP;

template<class T>
bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const ll INF = 1LL << 60;

class Edge {
private:
    int m_from, m_to, m_cost;

public:
    Edge(int f, int t, int c = 1) :
        m_from(f), m_to(t), m_cost(c) {}

    int from() const {
        return m_from;
    }

    int to() const {
        return m_to;
    }

    int cost() const {
        return m_cost;
    }

    Edge& operator=(const int x) {
        m_cost = x;
        return *this;
    }

    bool operator<(const Edge& e) const {
        return m_cost < e.cost();
    }
};

using Edges = vector<Edge>;
using Graph = vector<Edges>;

// 全点間最短路を求める。到達できない要素にはinfが格納されている前提。
void warshall_floyd(Graph& graph, int inf) {
    const int v = graph.size();
    for (int k = 0; k < v; k++) {
        for (int i = 0; i < v; i++) {
            for (int j = 0; j < v; j++) {
                //if (i == j || i == k || j == k) continue; // 自分と同じノードに対する距離に0を格納していたらこの処理は不要。
                if (graph[i][k].cost() == inf || graph[k][j].cost() == inf) continue;
                graph[i][j] = min(graph[i][j].cost(), graph[i][k].cost() + graph[k][j].cost());
            }
        }
    }
}

// 隣接行列を生成
Graph gen_graph(const int n, const int inf) {
    Graph g(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int cost = (i == j) ? 0 : inf;
            g[i].push_back(Edge(i, j, cost));
        }
    }
    return g;
}

signed main() {
    auto graph = gen_graph(4, INF);
    for (int i = 0; i < 3; i++) {
        int a, b; cin >> a >> b; a--, b--;
        graph[a][b] = graph[b][a] = 1;
    }
    warshall_floyd(graph, INF);

    bool ok = false;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (graph[i][j].cost() == 3) {
                ok = true;
            }
        }
    }
    cout << (ok ? "YES" : "NO") << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using ll=long long;
#define print(n) cout<<n<<endl
#define rep(i,a,n) for(int i=a;i<n;i++)
#define ALL(s) s.begin(),s.end()
#define P pair<ll,ll>
#define vl vector<ll>
#define vi vector<int>
#define vvl vector<vector<ll>>
#define vvi vector<vector<int>>
const int M=100111;
const int inf=1000000007;
const long long INF=1e18;
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
int ddx[8]={1,-1,0,0,1,-1,-1,1},ddy[8]={0,0,1,-1,1,-1,1,-1};

/*
vvl comb(int n, int r) {
	vvl v(n + 1,vl(n + 1, 0));
	for (int i = 0; i < v.size(); i++) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (int j = 1; j < v.size(); j++) {
		for (int k = 1; k < j; k++) {
			v[j][k] = (v[j - 1][k - 1] + v[j - 1][k]);
		}
	}
	return v;
}
*/


int main() {
	string s;
	cin>>s;
	int a=-1,b=-1;
	rep(i,0,s.size()-1){
		if(s[i]==s[i+1]){
			a=i+1,b=i+2;
		}
	}
	rep(i,0,s.size()-2){
		if(s[i]==s[i+2]){
			a=i+1,b=i+3;
		}
	}
	print(a<<" "<<b);
}

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

int main() {
  int n;
  cin >> n;
  int ntmp = n;
  int sum = 0;
  while (n) {
    sum += n % 10;
    n /= 10;
  }
  if (ntmp % sum) cout << "No" << endl;
  else cout << "Yes" << endl;
  return 0;
}


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

using namespace std;

long long n, a[200000], X, x;
long long ans = 10000000000000000LL;

int main(){
	cin >> n;
	for(int i = 0; i < n; ++i){
		cin >> a[i];
		X += a[i];
	}
	for(int i = 0; i < n - 1; ++i){
		x += a[i];
		ans = min(ans, abs(X-2*x));
	}
	cout << ans << endl;
}

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

const int INF = 1001001001;
const int mod = 1000000007;

ll pow(ll base, ll order) {
	ll ans = 1;
	rep(i,order - 1) ans *= base;
	return ans;
}

int gcd(int a, int b) {
	if (a < b) {
		int c = a;
		a = b;
		b = c;
	}
	if (b == 0) return a;
	return gcd (b, a % b);
}

int main() {
	int a, p;
	cin >> a >> p;

	int ans = 0;
	p += 3*a;
	ans = p/2;
	cout << ans << endl;
	
	return 0;
} 

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define N 200005
#define P 1000000007
using namespace std;
int i,j,k,l,s,n,m,S[N],f[N][3],F[5],ans,fa[N],si[N],dis[N],st[N],q[N],r,FA[N],tot,id[N],vis[N];
struct node {
	int tot,last[N],to[2*N],Next[2*N];
	inline void add(int x,int y) {
		Next[++tot]=last[x]; last[x]=tot; to[tot]=y;
	}
}A,B;
inline void dfs(int x,int y) {
	if (y==-1) y=x;
	FA[x]=y;
	st[x]=++tot;
	int gt=0,gtw=0;
	for (int i=A.last[x];i;i=A.Next[i]) if (si[A.to[i]]>gt) gt=si[A.to[i]],gtw=A.to[i];
	if (!gtw) return ;
	dfs(gtw,y);
	for (int i=A.last[x];i;i=A.Next[i]) if (A.to[i]!=gtw) dfs(A.to[i],-1);
}
inline bool cmp1(int x,int y) {
	return st[x]<st[y];
}
inline bool cmp(int x,int y) {
	return dis[x]>dis[y];
}
inline int quick(int x,int y) {
	int s=1;
	while (y) {
		if (y&1) s=1ll*s*x%P;
		x=1ll*x*x%P;
		y>>=1;
	}
	return s;
}
inline int get(int x,int y) {
	while (FA[x]!=FA[y]) {
		if (dis[FA[x]]>dis[FA[y]]) x=fa[FA[x]];
		else y=fa[FA[y]];
	}
	if (dis[x]>dis[y]) return y;
	return x;
}
inline void work(int x,int y) {
	if (x==y) {
		(ans+=quick(2,n+1-(y-x+1)))%=P;
		return ;
	}
	int r=0;
	sort(id+x,id+y+1,cmp1);
	for (int i=x;i<=y;i++) f[id[i]][1]=f[id[i]][0]=1;
	int stack=0;
	for (int i=x+1;i<=y;i++) {
		int lca=get(id[i-1],id[i]);
		if (!vis[lca]) vis[q[++r]=lca]=1;
		for (;stack;stack--) {
			if (dis[S[stack]]<=dis[lca]) break;
			if (dis[S[stack-1]]>dis[lca]&&stack>1) B.add(S[stack-1],S[stack]);
			else B.add(lca,S[stack]);
		}
		if (S[stack]!=lca||(!stack)) S[++stack]=lca;
	}
	while (stack>1) B.add(S[stack-1],S[stack]),stack--;
	for (int i=x+1;i<y;i++) {
		int L=get(id[i-1],id[i]),R=get(id[i],id[i+1]);
		if (dis[L]>dis[R]) B.add(L,id[i]);
		else B.add(R,id[i]);
	}
	B.add(get(id[x],id[x+1]),id[x]);
	B.add(get(id[y],id[y-1]),id[y]);
	sort(q+1,q+1+r,cmp);
	for (int i=1;i<=r;i++) {
		F[0]=1;
		F[1]=F[2]=0;
		for (int j=B.last[q[i]];j;j=B.Next[j]) {
			F[2]=(1ll*F[2]*(f[B.to[j]][0]+f[B.to[j]][1])+1ll*F[1]*f[B.to[j]][1])%P;
			F[1]=(1ll*F[1]*f[B.to[j]][0]+1ll*F[0]*f[B.to[j]][1])%P;
			F[0]=1ll*F[0]*f[B.to[j]][0]%P;
		}
		f[q[i]][0]=(F[0]+F[2])%P;
		f[q[i]][1]=F[1];
	}
	(ans+=1ll*f[q[r]][1]*quick(2,n+1-(y-x+1))%P)%=P;
	for (int i=1;i<=r;i++) B.last[q[i]]=vis[q[i]]=0;
	B.tot=0;
}
int main() {
	scanf("%d",&n);
	for (i=1;i<=n;i++) scanf("%d",&fa[i]),A.add(fa[i],i);
	for (i=n;i;i--) si[i]++,si[fa[i]]+=si[i];
	dis[0]=1;
	for (i=1;i<=n;i++) dis[i]=dis[fa[i]]+1;
	dfs(0,-1);
	for (i=1;i<=n;i++) id[i]=i;
	sort(id+1,id+1+n,cmp);
	ans=quick(2,n);
	for (i=1;i<=n;i=j) {
		j=i;
		while (dis[id[j]]==dis[id[i]]) j++;
		work(i,j-1);
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 44416
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
#define all(v) v.begin(), v.end()
#define repi(i, n, init) for (ll i = init; i < (n); i++)
#define repd(i, n, init) for (ll i = (n); i >= init; i--)
#define repm(i, m) for (auto i = m.begin(); i != m.end(); i++)
#define repb(bit, n, init) for (ll bit = init; bit < (1 << n); ++bit)

int main()
{
    double r;
    cin >> r;
    cout << fixed << setprecision(10) << r * r * M_PI << " " << fixed << setprecision(10) << r * M_PI * 2 << endl;
    return 0;
}


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

int main()
{
    int n;
    int i;
    long long int c, ans = 0;
    
    cin >> n;
    
    long long int a[n], b[n];
    
    for(i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }
    
    for(i = n-1; i >= 0; i--) {
        c = a[i] + ans;
        if(c % b[i] != 0) {
            ans += b[i] - (c % b[i]);
        }
    }
    
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 1792
#[allow(unused_imports)]
use {
   proconio::{fastout, input, marker::*},
   std::cmp::*,
   std::collections::*,
};

#[fastout]
fn main() {
   input! {
      n: usize,
   }
   let ans = 8 - (n-400)/200;
   println!("{}", ans);
}


Measured memory_bytes: 2160
#include <stdio.h>
#include <math.h>
typedef struct {
  double x;
  double y;
} P; 
void koch(int n,P P1,P p2);

int main()
{
  int i,n;
  P p1,p2;

  scanf("%d",&n);
  //ini
  p1.x=0;
  p1.y=0;
  p2.x=100;
  p2.y=0;
  //koch
  printf("%.8f %.8f\n",p1.x,p1.y);
  koch(n,p1,p2);
  printf("%.8f %.8f\n",p2.x,p2.y);

  return 0;
}

void koch(int n,P p1,P p2)
{
  P s,t,u;
  double th=M_PI*60.0/180.0;

  if(n==0) return;
  s.x=(2.0*p1.x+1.0*p2.x)/3.0;
  s.y=(2.0*p1.y+1.0*p2.y)/3.0;
  t.x=(1.0*p1.x+2.0*p2.x)/3.0;
  t.y=(1.0*p1.y+2.0*p2.y)/3.0;
  u.x=(t.x-s.x)*cos(th)-(t.y-s.y)*sin(th)+s.x;
  u.y=(t.x-s.x)*sin(th)+(t.y-s.y)*cos(th)+s.y;

  koch(n-1,p1,s);
  printf("%.8f %.8f\n",s.x,s.y);
  koch(n-1,s,u);
  printf("%.8f %.8f\n",u.x,u.y);
  koch(n-1,u,t);
  printf("%.8f %.8f\n",t.x,t.y);
  koch(n-1,t,p2);
}

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

using namespace std;

int main()
{
    long long N,K;
    cin>>N>>K;
    vector<int> h;
    h.assign(N,0);
    for(int i = 0;i<N;i++)
    {
        cin>>h[i];
    }
    sort(h.begin(),h.end());
    long long suma=0;
    for(int i = 0;i<N-K;i++)
    {
        suma+=h[i];
    }
    cout<<suma;
}


Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
int t,n,m;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
vvi in;
bool check(int a,int b){return a>=0&&b>=0&&a<n&&b<n;}
void f(int a,int b){
	in[a][b]^=1;
	rep(i,4){
		int nx=a+dx[i];
		int ny=b+dy[i];
		if(!check(nx,ny))continue;
		if(in[nx][ny]==t)f(nx,ny);
	}
}
int main(){
	cin>>n>>m;
	in=vvi(n,vi(n));
	rep(i,n)rep(j,n)cin>>in[i][j];
	while(m--){
		int q;
		cin>>q;
		int a,b,c,d;
		if(q==0){
			cin>>a>>b>>c>>d;
			a--;b--;
			rep(i,d/90){
				vvi tmp=in;
				rep(i,c)rep(j,c)tmp[i+a][j+b]=in[a+c-j-1][b+i];
				in=tmp;
			}
		}else if(q==1){
			cin>>a>>b>>c;
			a--;b--;
			rep(i,c)rep(j,c)in[i+a][j+b]^=1;
		}else if(q==2){
			cin>>a;
			a--;
			in[a].pb(in[a][0]);
			in[a].erase(in[a].begin());
		}else if(q==3){
			cin>>a;a--;
			in[a].insert(in[a].begin(),in[a][n-1]);
			in[a].erase(in[a].end()-1);
		}else if(q==4){
			cin>>a>>b;a--;b--;
			t=in[a][b];
			f(a,b);
		}
	}
	rep(i,n){cout<<in[i][0];rep(j,n-1)cout<<" "<<in[i][j+1];cout<<endl;}
}

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

int main(){
	string s;
    cin>>s;
    long long int i=0,sum=0;
    while(s[i]){
        sum+=s[i]-'0';
        //cout<<s[i]-'0'<<" ";
        i++;
    }
    if(sum%9==0){
        cout<<"Yes";
    }
    else{
        cout<<"No";
    }
    return 0;
}

Measured memory_bytes: 3732
h=int(input())
w=int(input())
n=int(input())         
if h>w:
  if n%h==0:
    ct=n//h
  else:
    ct=n//h+1
else:
  if n%w==0:
    ct=n//w
  else:
    ct=n//w+1
print(ct)

Measured memory_bytes: 3060
from itertools import product
N = int(input())

for h in range(1, 3501):
    for n in range(1, 3501):
        a = (4 * h * n - N * n - N * h)
        if a > 0 and (N * h * n) % a == 0:
            w = (N * h * n) / a
            int_w = int(w)
            if w == int_w:
                print(n,h,int_w)
                exit()


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

int main() {
  ll n,k;
  cin >> n >> k;
  ll m = n % k;
  cout << min(m, k - m) << endl;
  return 0;
}


Measured memory_bytes: 3580
#include <bits/stdc++.h>
#define rep(i,m,n) for(int i=m;i<n;i++)
#define co(n) cout<<n<<endl
#define all(n) (n).begin(),(n).end()
#define pb(n,m) n.push_back(m)
#define pi(n,m) n.insert(n.begin(),m);
#define ee(n) n.erase(n.end()-1)
#define eb(n) n.erase(n.begin())
#define check(n) reverse(all(n));rep(z,0,n.size())cout<<n[z];co("");reverse(all(n));
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int main(){
  ll n,m,c=0,d=0,p;
  string s;
  cin>>n>>m;
  pair<ll,bool> a[n];
  rep(i,0,n){
    a[i].first=0;
    a[i].second=false;
  }
  
  rep(i,0,m){
    cin>>p>>s;
    if(s=="WA" && a[p-1].second==false){
      a[p-1].first++;
    }
    else if(s=="AC"){
      a[p-1].second=true;
    }
  }
  rep(i,0,n){
    if(a[i].second==true){
      d++;
      c+=a[i].first;
    }
  }
  co(d<<" "<<c);
      
  return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e9;
const int N = 200000;



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

    int n;
    cin >> n;
    string s;
    int c = 0, c1 = 0, c2 = 0, c3 = 0;
    for(int i = 0; i < n; i++){
        cin >> s;
        if(s == "AC"){ c++;}
        else if(s == "WA"){ c1++;}
        else if(s == "TLE"){ c2++;}
        else if(s == "RE"){ c3++;}
    }
    cout << "AC " << "x " << c << endl;
    cout << "WA " << "x " << c1 << endl;
    cout << "TLE " << "x " << c2 << endl;
    cout << "RE " << "x " << c3 << endl;
    return 0;
}


Measured memory_bytes: 3652
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

ans=0
for i in range(N):
    ans += min(A[i],B[i])
    if B[i]>A[i]:
        sarani = min(A[i+1],B[i]-A[i])
        A[i+1] -= sarani
        ans += sarani
print(ans)

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

int main() {
   char S[3];
   int count = 0;

   scanf("%s", S);

   for(int i = 2; i > 0; i--) {
      for(int f = 0; f <= i; f++) {
         if(S[i] != S[f]) {
            count++;
         }
      }
   }
   if(count > 0) {
      printf("Yes\n");
   }else {
      printf("No\n");
   }
   return 0;
}



Measured memory_bytes: 1556
N, K = map(int, input().split())

sunukes = [0] * N

for _ in range(K):
    di = int(input())
    Ai = list(map(int, input().split()))
    for item in Ai:
        sunukes[item-1] += 1

ans = 0

for i in sunukes:
    if i == 0:
        ans += 1

print(ans)


Measured memory_bytes: 9052
#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
LL dp[5001][5001];
struct people{
	LL p=0,h=0;
	bool operator<(people b){
		return h+p<b.h+b.p;
	}
};
int main(){
	int n;
	cin>>n;
	people p[n];
	for(int i=0;i<n;i++) cin>>p[i].h>>p[i].p;
	sort(p,p+n);
	for(int i=0;i<n;i++) for(int j=1;j<=n;j++) dp[i][j]=INT_MAX;
	dp[0][1]=p[0].p;
	//for(int i=0;i<n;i++) dp[i][0]=0;

	for(int i=1;i<n;i++){
		for(int j=1;j<=i+1;j++){
			if(dp[i-1][j-1]<=p[i].h)
				dp[i][j]=min(dp[i-1][j-1]+p[i].p,dp[i-1][j]);
			dp[i][j]=min(dp[i][j],dp[i-1][j]);
		}
		//if(dp[i-1][i]<=p[i].h) dp[i][i+1]=dp[i-1][i]+p[i].p;
	}
	int cnt=0;
	/*
	 *for(int i=0;i<n;i++){
	 *    for(int j=0;j<=n;j++){
	 *        cout<<dp[i][j]<<" ";
	 *    }
	 *    puts("");
	 *}
	 */
	for(int i=1;i<=n;i++) if(dp[n-1][i]<INT_MAX) cnt++;
	cout<<cnt<<"\n";
	return 0;
}


Measured memory_bytes: 195712
#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long

using namespace std;

int main() {
	ll a, b, c, x, y;
	cin >> a >> b >> c >> x >> y;
	ll sum = 0, z = min(x, y);
	for (ll i = 0; i < z; i++) {
		sum += min(2 * c, a + b);
	}
	ll m = max(x, y);
	if (m == x) {
		for (ll i = 0; i < abs(x - y); i++) {
			sum += a;
		}
	}
	else {
		for (ll i = 0; i < abs(x - y); i++) {
			sum += b;
		}
	}
	ll sum2 = 0;
	for (ll i = 0; i < m; i++) {
		sum2 += min(2 * c, a + b);
	}

	cout << min(sum, sum2) << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pb			push_back
#define all(v)			((v).begin()), ((v).end())
#define SZ(v)			((int)((v).size()))
#define clr(v, d)		memset(v, d, sizeof(v))
#define has(c,i) 		((c).find(i) != end(c))
#define hastr(s, c)		((s).find(c) != string::npos)
template <class U, class V>
istream& operator>>(istream& is, pair<U, V>& p) {
  is >> p.first >> p.second;
  return is;
}
template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (auto& x : v) {
    is >> x;
  }
  return is;
}
template <class T>
ostream& operator<<(ostream& os, vector<T>& v) {
  for (auto& x : v) {
    os << x << " ";
  }
  return os;
}
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
const int dr[] { -1, -1, 0, 1, 1, 1, 0, -1 };
const int dc[] { 0, 1, 1, 1, 0, -1, -1, -1 };
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;

int main() {
#ifndef	ONLINE_JUDGE
//	freopen("input.in", "r", stdin);
//	freopen("output.out", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll n;
    cin >> n;
    cout << n * n + n * n * n + n << endl;
    return 0;
}


Measured memory_bytes: 3644
#include<iostream>
#include<vector>
using namespace std;
int main()
{
	int n,m;
	cin>>n>>m;
	vector<int>N(51);
	for(int i=0;i<m;++i){
		int a,b;
		cin>>a>>b;
	N[a]=N[a] + 1;
	N[b]=N[b] + 1;
	}
	for(int i=1;i<=n;++i){
		cout<<N[i]<<endl;
	}
}

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

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

ll mod = 1e9 + 7;
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; }
const ll inf = 1ll << 60;

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    priority_queue<pair<ll, ll>> que;
    ll t, d;
    rp(i, 0, n) {
        scanf("%lld%lld", &t, &d);
        que.push(make_pair(d, t));
    }
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>> > que2;
    int count = 0;
    vector<int> list(n + 10);
    ll var = 0;
    ll ans = 0ll;
    while(count < k) {
        pair<ll, ll> p = que.top();
        que2.push(p);
        ans += p.first;
        if(list.at(p.second) == 0) var++;
        list.at(p.second)++;
        que.pop();
        count ++;
    }
    ll temp = ans;//暫定的なおいしさ基礎点
    ans += var*var;

    while(!que.empty()){
        pair<ll, ll> p = que.top(); que.pop();
        if(list.at(p.second)) continue;
        list.at(p.second)++;
        ll m = -1;
        while(!que2.empty()){
            pair<ll, ll> p2 = que2.top(); que2.pop();
            if(list.at(p2.second) > 1) {
                m = p2.first;
                list.at(p2.second)--;
                break;
            }
        }
        if(m == -1) break;
        temp -= m;
        temp += p.first;
        var ++;
        chmax(ans, temp+var*var);
    }
    printf("%lld", ans);
    return 0;
}

Measured memory_bytes: 5232
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = Integer.parseInt(sc.next());
        int b = Integer.parseInt(sc.next());
        if(a>9 || b> 9){
            System.out.println(-1);
        }else{
            System.out.println(a*b);
        }
        sc.close();
    }
    
}

Measured memory_bytes: 21716
def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, A, B = read_ints()
    X = read_ints()
    answer = 0
    for i in range(1, N):
        answer += min(A*(X[i]-X[i-1]), B)
    return answer


if __name__ == '__main__':
    print(solve())


Measured memory_bytes: 84332
import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner sn = new Scanner(System.in);
        String S = sn.next();
        if(S.length() == 3) System.out.println(S);
        else{
            Random r = new Random();
            int rValue = r.nextInt(S.length()-3);
            System.out.println(S.substring(rValue, rValue+3));
        }

    }
}

Measured memory_bytes: 35588
import heapq
n, m = map(int, input().split())
A = list(map(int, input().split()))
for i in range(n):
  A[i] = -A[i]
B = heapq.heapify(A)
i = 0
while i < m:
  h = heapq.heappop(A) 
  heapq.heappush(A, -(-h//2))
  i += 1
print(-sum(a for a in list(A)))

Measured memory_bytes: 14180
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

int N;
map<int, int> lines;
string op[51], v1[51], v2[51], v3[51];
int env[256];

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N;
  vector<char> var_names;
  rep(i, N) {
    int line;
    cin >> line >> op[i];
    lines[line] = i;
    if (op[i] == "HALT") {}
    else if (op[i] == "SET" || op[i] == "IF") cin >> v1[i] >> v2[i];
    else cin >> v1[i] >> v2[i] >> v3[i];
    if (v1[i].size() && !('0' <= v1[i][0] && v1[i][0] <= '9')) var_names.pb(v1[i][0]);
    if (v2[i].size() && !('0' <= v2[i][0] && v2[i][0] <= '9')) var_names.pb(v2[i][0]);
    if (v3[i].size() && !('0' <= v3[i][0] && v3[i][0] <= '9')) var_names.pb(v3[i][0]);
  }
  op[N] = "HALT";
  rep(i, 256) env[i] = -1;
  for (char s : var_names) env[s] = 0;
  int steps = 0;
  int cur = 0;
  auto eval = [&](string s) {
    if ('0' <= s[0] && s[0] <= '9') return stoi(s);
    else return env[s[0]];
  };
  auto halt = [&]() {
    rep(c, 256) {
      if (env[c] == -1) continue;
      cout << (char)c << "="<<env[c]<<"\n";
    }
    exit(0);
  };
  auto assign = [&](string s, int val) {
    if (val < 0 || val >= 16) halt();
    env[s[0]] = val;
  };
  while (steps++ <= (1<<20)*30) {
    if (op[cur] == "ADD") {
      assign(v1[cur], eval(v2[cur]) + eval(v3[cur]));
    }
    else if (op[cur] == "SUB") {
      assign(v1[cur], eval(v2[cur]) - eval(v3[cur]));
    }
    else if (op[cur] == "SET") {
      assign(v1[cur], eval(v2[cur]));
    }
    else if (op[cur] == "IF") {
      if (lines.find(stoi(v2[cur])) == lines.end()) halt();
      int dest = lines[stoi(v2[cur])];
      if (eval(v1[cur]) != 0) {
        cur = dest;
        continue;
      }
    }
    else if (op[cur] == "HALT") halt();
    cur++;
  }
  cout << "inf\n";
  return 0;
}

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

int main(){
	int k,s;
	cin>>k>>s;
	
	int cnt=0;
	for(int a=0;a<=k;++a){
		for(int b=0;b<=k;++b){
			int c=s-(a+b);
			if(0<=c&&c<=k) cnt++;
		}
	}
	
	cout<<cnt<<endl;
	return 0;
}

Measured memory_bytes: 256
import sys
def single_input(F): return F.readline().strip("\n")
def line_input(F): return F.readline().strip("\n").split()
  
def solve():
    F = sys.stdin
    N = int(single_input(F))
    S = [int(s) for s in line_input(F)]
    
    maxpoint = 0
    for c in range(1, N//2):
        s, l = 0, N-1
        point = 0
        if (N-1) % c == 0:
            while l > s and l > c:
                point += S[s] + S[l]
                maxpoint = max(point, maxpoint)
                s += c
                l -= c
        else:
            while l != s and l > c:
                point += S[s] + S[l]
                maxpoint = max(point, maxpoint)
                s += c
                l -= c
    print(maxpoint)
    return 0
  
if __name__ == "__main__":
    solve()

Measured memory_bytes: 14468
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < (n); ++i)

using namespace std;

int main(void){

  int A, B, C, X;
  cin >> A >> B >> C >> X;

  int cnt = 0;

  REP(x, min(A, X / 500) + 1){
    REP(y, min(B, (X - 500 * x) / 100) + 1){
      int W = X - 500 * x - 100 * y;
      if(W / 50 <= C && W % 50 == 0){
	++cnt;
      }
    }
  }

  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 256
N = int(input())
s = []
for i in range(N):
  s.append([int(x) for x in input().split()])
import math
num = math.factorial(N)
n = N-1
p = sum(range(N))
a = num * n//p
#print(a)

d = 0
for i in range(len(s)-1):
  t = s[i]
  for j in range(i+1,len(s)):
    k = s[j]
    d += math.sqrt((t[0]-k[0])**2+(t[1]-k[1])**2)
print(a*d/num)

Measured memory_bytes: 38384
#include <set>
#include <cstdio>
#include <string>
 
using namespace std;
 
int main()
{
    int N; char S1[7], S2[7];
 
    scanf("%d", &N);
 
    set<string> dictionary;
 
    for (int i = 0; i < N; i++)
    {
        scanf("%s %s", S1, S2);
 
        if (S1[0] == 'i')
        {
            dictionary.insert(S2);
        }
        else
        {
            if (dictionary.find(S2) != dictionary.end())
            {
                printf("yes\n");
            }
            else
            {
                printf("no\n");
            }
        }
    }
 
    return 0;
}

Measured memory_bytes: 28592
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <tuple>
#include <cassert>

using namespace std;

#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i)
#define pb(e) push_back(e)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define mp(a,b) make_pair((a), (b))
#define mt(a,b,c) make_tuple((a),(b),(c))

typedef long long ll;

int main(){
    int n; cin >> n;
    vector<int> v(n); rep(i,n) cin >> v[i];
    int sum = 0; rep(i,n) sum += v[i];
    int tsum = v[0];
    int ans = abs(sum - tsum - tsum);;
    for(int i=1; i<n;i++){
        tsum += v[i];
        ans = min(ans, abs(sum -tsum -tsum));
    } 
    cout << ans << endl;
    return 0;
}

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

int main() {
  ios::sync_with_stdio(0);
	cin.tie(0);
  long long n , a , b;
  long long p;
  long long c = 0;

  cin >> n >> a >> b;

  cout << n/(a+b)*a+min(n%(a+b), a);
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>
struct Artist {
	int employ, satisfaction;
};
int main() {
	while (true) {
		int limit, n, m, x; std::cin >> limit >> n >> m >> x; if (n == 0) return 0;
		std::vector<Artist> secret(n); 
		for (auto& s : secret) {
			std::cin.ignore(std::numeric_limits<std::streamsize>::max(), ' ');
			std::cin >> s.employ >> s.satisfaction;
		}
		std::vector<std::vector<int>> memo(x, std::vector<int>(limit + 1, -1));
		for (auto c = 0; c < m; ++c) {
			Artist a;
			std::cin.ignore(std::numeric_limits<std::streamsize>::max(), ' ');
			std::cin >> a.employ >> a.satisfaction;
			for (int j = limit - a.employ; j >= 0; --j) {
				if (memo[x - 1][j] != -1) memo[x - 1][j + a.employ] = std::max(memo[x - 1][j + a.employ], memo[x - 1][j] + a.satisfaction);
			}
			for (int i = x - 2; i >= 0; --i) {
				for (int j = limit - a.employ; j >= 0; --j) {
					if (memo[i][j] != -1) memo[i + 1][j + a.employ] = std::max(memo[i + 1][j + a.employ], memo[i][j] + a.satisfaction);
				}
			}
			memo[0][a.employ] = std::max(memo[0][a.employ], a.satisfaction);
		}
		for (auto i = 1; i < memo[x - 1].size(); ++i) memo[x - 1][i] = std::max(memo[x - 1][i], memo[x - 1][i - 1]);
		int max = 0L;
		for (auto i = 0; i < secret.size(); ++i) {
			int employ = secret[i].employ, satisfaction = secret[i].satisfaction;
			if (employ <= limit && memo[x - 1][limit - employ] != -1) max = std::max(max, satisfaction + memo[x - 1][limit - employ]);
			for (auto j = 0; j < i; ++j) {
				int e = employ + secret[j].employ, s = satisfaction + secret[j].satisfaction;
				if (e <= limit && memo[x - 1][limit - e] != -1) max = std::max(max, s + memo[x - 1][limit - e]);
			}
		}
		std::cout << max << std::endl;
	}
}



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

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i=0;i<N;i++) {
   cin >> A.at(i);
  }
  sort (A.begin(),A.end());
  reverse (A.begin(),A.end());
  int answer = 0;
  int i=0;
  while(i<N) {
    answer += A.at(i);
    i += 2;
  }
  i = 1;
  while(i<N) {
    answer -= A.at(i);
    i += 2;
  }
  cout << answer << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define M 1000000007
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pie acos(-1)
#define loop(i,a,n) for(int i=a;i<n;i++)
#define trav(a,x) for(auto &a:x)
#define vi vector<int>
#define vl vector<ll>
#define pii pair<ll,ll>
#define endl "\n"
int n,to;
ll dp[101][100001];
ll ans(int rem,int item,vi &w,vl& v)
{
   
    if(item ==n+1)
    return 0; 
    if(rem<w[item])
    return ans(rem,item+1,w,v);
    ll &memo=dp[item][rem];
    if(memo!=-1)
    return memo;
    return memo=max(ans(rem,item+1,w,v),v[item]+ans(rem-w[item],item+1,w,v));
}
void solve()
{
    cin>>n>>to;
    memset(dp,-1,sizeof(dp));
    vi w(n+1);
    vl v(n+1);
    loop(i,1,n+1)
    cin>>w[i]>>v[i];
    cout<<ans(to,1,w,v);
}
int main() {
	// your code goes here
	io;
    solve();
	return 0;
}


Measured memory_bytes: 79232
import sys
sys.setrecursionlimit(1000000)
 
n, m = map(int, input().split())
g = [[] for _  in range(n)]
for _ in range(m):
  x, y = map(int, input().split())
  x, y = x -1, y-1
  g[x].append(y)  
 
# dp[v]: ノードvを起点にしたときの、Gの有効パスの長さの最大値
dp = [-1]*n
def rec(v):
  if dp[v] != -1:
    return dp[v]
  else:
    res = 0
    for u in g[v]:
      res = max(res, rec(u)+1)
    dp[v] = res
    return dp[v]
  
for i in range(n):
  rec(i)
print(max(dp))

Measured memory_bytes: 59056
#include<iostream>
using namespace std;
int main(){
	short a1,a2,b1,b2;
	cin>>a1>>a2>>b1>>b2;
	if(a1+a2>b1+b2)cout<<"Left";
	if(a1+a2<b1+b2)cout<<"Right";
	if(a1+a2==b1+b2)cout<<"Balanced";
	cout<<endl;
	return 0;
} 

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

#define ll            long long
#define pb            push_back
#define si            set <int>
#define F             first
#define S             second
#define mii           map<int ,int >
#define msi           map<string,int >
#define mis           map<int , string>
#define fr(i,a,b)     for(int  i=a;i<=b;i++)
#define loop(i,n)     for(int i=0;i<n;i++)
#define all(v)        v.begin(),v.end()
#define vi            vector<int >
#define vii           vector<pair<int , int >>
#define vs            vector<string>
#define sz(x)         (int )x.size()
#define M             1000000007
#define mp            make_pair
#define input(arr,n)  loop(i,n) cin>>arr[i]
#define output(arr,n) loop(i,n) cout<<arr[i]<<" "
#define mod           998244353
#define sof           sizeof
using namespace std;
int gcd(int a,int b){
  if(b==0)return a;
  return gcd(b,a%b);
}

bool isPrime(int num){
    
    if(num==2) return true;
    if(num<2 || num%2==0) return false;
    for(int i = 3; i*i <=num; i+=2) {
       if(num % i == 0) {
          
          return false;
       }
    }
    return true;
   
}

bool comp(const pair<int,int> &a,const pair<int,int> &b){
  return a.F>b.F;
}

vector<vector<int>> L(3005,vector<int>(3005,-1));
string a,b;



const int N=1e9+7;

void solve(){
  
  int n,w;
  cin>>n>>w;
  int grid[n+1][w+1];
  
  vector<string> v(n+1);
  string s;
  fr(i,1,n){
    cin>>s;
    s=" "+s;
    v[i]=s;
    //cout<<v[i]<<'\n';
  }
  //cout<<v[4][1];

  grid[1][1]=1;
  fr(i,1,n){
    fr(j,1,w){
      if(i==1 && j==1) continue;
      else if(v[i][j]=='#'){
        //cout<<i<<" "<<j<<" ";
        //cout<<"mai aya\n";
        grid[i][j]=0;
      }
      else{
        if(i==1 && j>1){
          grid[i][j]=grid[i][j-1];
        }
        else if(i>1 && j==1){
          grid[i][j]=grid[i-1][j];
        }
        else
        grid[i][j]=(grid[i-1][j]+grid[i][j-1])%N;
      }
    }
  }
  
  cout<<grid[n][w];

}




signed main()   
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); 
  cout.tie(0);
  #ifndef ONLINE_JUDGE
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout); 
  #endif  

  int t;
  t=1;
  //cin>>t;
  loop(i,t){

      solve();
      if(i<t-1) cout<<"\n";
  }

  
  
  //directed graph
    



}
  


  



Measured memory_bytes: 43932
// lcmとかはg++ -std=c++17 default.cppみたいなかんじで
//vector<vector<ll>> piyo(tate,vector<ll> (yoko));

#include <bits/stdc++.h>
#define mod 1000000007
#define INF 100000001
#define ll long long
#define ln cout<<endl;
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define double long double
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
using namespace std;
int dp[120][1050];
bool my_compare(pair<ll, string> a, pair<ll , string> b) {
    // 基本はfirstで比較
    if(a.first != b.first){
         //return a.first < b.first; // 昇順
        return a.first > b.first; // 降順
    }

    // それ以外はsecondで比較
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        // どちらも同じ
        return true;
    }
}

int main() {
    cin.tie(0);
   	ios::sync_with_stdio(false);
    //double mini=INF;
    int maxi=0,f=0,sum=0,mini=INF;
    string str,str1,str2;
    int i,m;
    int n;
    int a,b,d,c;
    int e,weight;
    cin>>n>>m;
    vector<string> stra(n);
    rep(i,n) cin>>stra[i];
    sort(stra.begin(),stra.end());
    rep(i,n) cout<<stra[i];
    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#include<unordered_map>
#pragma warning(disable:4996)
using namespace std;

struct aa {
	int now;
	int dis;
	int gas;
};
class Compare {
public:
	//keiroが昇順に並ぶ
	bool operator()(const aa&l, const aa&r) {
		return l.dis> r.dis;
	}
};
int main() {
	while (1) {
		int N, M, cap; cin >> N >> M >> cap;
		cap *= 10;
		if (!N)break;
		map<string, int>mp;
		int num = 2;
		vector<vector<pair<int, int>>>edges(6000);
		string sta, goa; cin >> sta >> goa; mp[sta] = 0; mp[goa] = 1;
		for (int i = 0; i < N; ++i) {
			string f, t; cin >> f >> t;
			int dis; cin >> dis;
			if (!mp.count(f)) {
				mp[f] = num++;
			}
			if (!mp.count(t)) {
				mp[t] = num++;
			}
			const int fid = mp[f];
			const int tid = mp[t];
			edges[fid].push_back(make_pair(tid, dis));
			edges[tid].push_back(make_pair(fid, dis));
		}
		edges.resize(mp.size());
		vector<bool>stat(edges.size(),false);
		for (int i = 0; i < M; ++i) {
			string st; cin >> st;
			if (mp.count(st)) {
				stat[mp[st]] = true;
			}
		}
		vector<vector<int>>mindiss(mp.size(), vector<int>(cap + 1, 99999999));
		priority_queue<aa, vector<aa>, Compare>que;
		que.push(aa{ 0,0,cap });
		mindiss[0][cap] = 0;

		while (!que.empty()) {
			aa atop(que.top());
			que.pop();
			const int pregas = atop.gas;
			const int nowdis = atop.dis;
			if (atop.now == 1)break;
			
			for (auto i : edges[atop.now]) {
				if (pregas >= i.second) {
					const int newid = i.first;
					const int newgas = stat[newid]?cap:atop.gas - i.second;
					const int newdis = nowdis + i.second;
					if (mindiss[newid][newgas]> newdis) {
						mindiss[newid][newgas] = newdis;
						que.push(aa{ newid, newdis ,newgas });
					}
				}
			}
		}
		int ans = 99999999;
		for (int i = 0; i < cap + 1; ++i) {
			ans = min(mindiss[1][i], ans);
		}
		if (ans == 99999999) {
			cout << -1 << endl;
		}
		else {
			cout << ans << endl;

		}
	}
	return 0;
}

Measured memory_bytes: 51604
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pi acos(-1)
#define mod 1000000007
using namespace std;

int dp[3001][3001];
string a, b;

void funk(int i, int j, string &s, string curr){
    if(i == 0 || j == 0){
        s = curr;
        return ;
    }
    if(a[i-1] == b[j-1]){
        curr += a[i-1];
        funk(i-1,j-1,s,curr);
        return;
    }
    if(dp[i-1][j] < dp[i][j-1]){
        funk(i,j-1,s,curr);
    }else{
        funk(i-1,j,s,curr);
    }
    return;
}

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

    cin >> a >> b;
    int n = a.length(), m = b.length();
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(a[i] == b[j]){
                dp[i + 1][j + 1] = dp[i][j] + 1;
            }
            dp[i+1][j+1] = max(dp[i + 1][j + 1], max(dp[i + 1][j], dp[i][j + 1]));
        }
    }
    string ans = "";
    string s;
    funk(n, m, ans, s);
    reverse(ans.begin(), ans.end());
    cout << ans;
    return 0;
}


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

int main()
{
    ll n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    ll sum = (ll) abs(a[0]);
    repl(i, 1, n) {
        sum += (ll) abs(a[i] - a[i - 1]);
    }
    sum += (ll) abs(a[n - 1]);
    ll ans = sum;
    ans = sum - abs(a[0]) - abs(a[1] - a[0]) + abs(a[1]);
    cout << ans << endl;
    ans = sum;
    repl(i, 1, n - 1) {
        ans = sum - abs(a[i] - a[i - 1]) - abs(a[i + 1] - a[i]) + abs(a[i + 1] - a[i - 1]);
        cout << ans << endl;
        ans = sum;
    }
    ans = sum - abs(a[n - 1]) - abs(a[n - 1] - a[n - 2]) + abs(a[n - 2]);
    cout << ans << endl;
    return 0;
}


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

using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr int inf = 1<<30;
constexpr int mod = 1e9+7;
constexpr ll infl = 1ll<<60;

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    int sx,sy,tx,ty;
    cin>>sx>>sy>>tx>>ty;
    for(int i=0;i<tx - sx; ++i)cout << "R";
    for(int i=0;i<ty - sy;++i)cout << "U";
    for(int i=0;i<tx - sx;++i)cout << "L";
    for(int i=0;i<ty - sy;++i)cout << "D";
    cout  << "D";
    for(int i=0;i<tx - sx +1; ++ i)cout << "R";
    for(int i=0;i<ty - sy + 1;++i)cout << "U";
    cout  << "L";
    cout << "U";
    for(int i=0;i<tx - sx + 1; ++ i)cout << "L";
    for(int i=0;i<ty - sy + 1;++i)cout << "D";
    cout << "R";
    
    return 0;
}

Measured memory_bytes: 3560
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
int prime[1000001];
int pricecheck[2000001];
int main(){
    for(int i=2;i<=1000000;i++)prime[i]=1;
    for(int i=2;i<=1000;i++){
        if(!prime[i])continue;
        for(int j=2;;j++){
            if(1000000<i*j)break;
            prime[i*j]=0;
        }
    }
    while(1){
        int N,X;
        cin>>N>>X;
        if(N==0&&X==0)break;
        int price[30];
        for(int i=0;i<N;i++)cin>>price[i];
        for(int i=0;i<=1000000;i++)pricecheck[i]=0;
        pricecheck[0]=1;
        for(int i=0;i<1000000;i++){
            if(pricecheck[i]){
                for(int j=0;j<N;j++){
                    pricecheck[i+price[j]]=1;
                }
            }
        }
        for(int i=X;;i--){
            if(i==1){
                puts("NA");
                break;
            }
            if(pricecheck[i]&&prime[i]){
                printf("%d\n",i);
                break;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 14872
#include <bits/stdc++.h>
using namespace std;
int n;
int main() {
    cin >> n;
    vector<int> color(9, 0);
    for(int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        int no = a / 400;
        if(no >= 8) {
            color.at(8)++;
        }else {
            color.at(no)++;
        }
    }

    int cnt = 0;
    for(int i = 0; i < 8; ++i) {
        if(color.at(i) != 0) cnt++;
    }
    int mcnt = cnt+color.at(8);
    if(cnt == 0) cnt = 1;

    cout << cnt << " " << mcnt << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;

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

int main()
{
	
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",a+i);
	dp[2]=abs(a[2]-a[1]);
	for(int i=3;i<=n;i++)
		dp[i]=min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2]));
	cout<<dp[n]<<'\n';
	
	return 0;
}

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

const int N = 300010;
const int mod = 1e9 + 7;

int dp[N][3][3]; char s[N];

int main() {
    scanf("%s", s + 1), dp[0][0][0] = 1; int n = strlen(s + 1);
    for (int i = 1; i <= n; i++) {
        for (int a = 0; a <= 2; a++)
            for (int b = 0; b <= 2; b++) {
                if (s[i] != '1') {
                    if (b == 2) dp[i][a][b - 1] = (dp[i][a][b - 1] + dp[i - 1][a][b]) % mod;
                    else dp[i][a][b + 1] = (dp[i][a][b + 1] + dp[i - 1][a][b]) % mod;
                } 
                if (s[i] != '0') {
                    if (b) dp[i][a][b - 1] = (dp[i][a][b - 1] + dp[i - 1][a][b]) % mod;
                    else dp[i][min(2, a + 1)][b] = (dp[i][min(2, a + 1)][b] + dp[i - 1][a][b]) % mod;
                }
            }
    }
    int res = 0;
    for (int a = 0; a <= 2; a++)
        for (int b = 0; b <= a; b++) res = (res + dp[n][a][b]) % mod;
    printf("%d\n", res);
}

Measured memory_bytes: 11136