akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long int MOD = 1000000007;

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

int main(void){
    int N, K; cin >> N >> K;
    vector<int> A(N); for(int i = 0; i < N; i++) cin >> A[i];
    
    int g = 0;
    int max_A = 0;
    for(int i = 0; i < N; i++){
        g = __gcd(g, A[i]);
        max_A = max(max_A, A[i]);
    }
    
    if (K % g == 0 && K <= max_A) cout << "POSSIBLE" << endl;
    else cout << "IMPOSSIBLE" << endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
//cin.sync_with_stdio(false);

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define rep(i,n) FOR(i,0,n)

typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> Vector;
typedef vector<Vector>	DVector;

int main(int argc, char const *argv[])
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	int x;
	cin >> x;
	int max = 0;
	int num;

	rep(i, 1000){
		FOR(j, 2, 10){
			num = pow(i, j);
			if( num <= x ){
				//cout << num << endl;
				if(max <= num)	max = num;
			}else{
				break;
			}
		}
	}
	cout << max << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int Inf = 1000000000;
constexpr ll INF= 1e18;
constexpr ll MOD = 1000000007;
const double PI = 3.1415926535897;
typedef pair<ll,ll> P;

int main() {
    int A,B,Q;
    cin >> A >> B >> Q;
    vector<ll> S(A + 2);
    S.at(0) = -INF;
    for(int i = 1;i < A + 1;i++) {
        cin >> S.at(i);
    }
    S.at(A + 1) = INF;
    vector<ll> T(B + 2);
    T.at(0) = -INF;
    for(int i = 1;i < B + 1;i++) {
        cin >> T.at(i);
    }
    T.at(B + 1) = INF;
    for(int i = 0;i < Q;i++) {
        ll x;
        cin >> x;
        ll ret = INF;
        auto itr1 = upper_bound(S.begin(),S.end(),x);
        auto itr2 = upper_bound(T.begin(),T.end(),x);
        int a = itr1 - S.begin();
        int b = itr2 - T.begin();
        ret = min(ret,max(S.at(a),T.at(b)) - x);
        ret = min(ret,x - min(S.at(a - 1),T.at(b - 1)));
        ret = min(ret,min(S.at(a) - x,x - T.at(b - 1)) + (S.at(a) - T.at(b - 1)));
        ret = min(ret,min(T.at(b) - x,x - S.at(a - 1)) + (T.at(b) - S.at(a - 1)));
        cout << ret << endl;
    }
}

Measured memory_bytes: 2944
#include<iostream>
using namespace std;
long mod=1e9+7;
long F[2<<20],I[2<<20];
long power(long a,long b){return b?power(a*a%mod,b/2)*(b%2?a:1)%mod:1;}
long f(int R,int C)
{
	long ret=0;
	for(long c=0;c<=C;c++)
	{
		(ret+=F[c+R+1]*I[c+1]%mod*I[R]%mod)%=mod;
	}
	return ret;
}
main()
{
	F[0]=1;
	for(long i=1;i<2<<20;i++)F[i]=F[i-1]*i%mod;
	I[(2<<20)-1]=power(F[(2<<20)-1],mod-2);
	for(long i=(2<<20)-1;i--;)I[i]=I[i+1]*(i+1)%mod;
	int r1,c1,r2,c2;
	cin>>r1>>c1>>r2>>c2;
	long ans=f(r1-1,c1-1)-f(r2,c1-1)-f(r1-1,c2)+f(r2,c2);
	ans=(ans%mod+mod)%mod;
	cout<<ans<<endl;
}


Measured memory_bytes: 33024
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
const ll N = 100005;
char en = '\n';
ll inf = 1e16;
ll mod = 1e9 + 7;
ll power(ll x, ll n, ll mod) {
  ll res = 1;
  x %= mod;
  while (n) {
    if (n & 1)
      res = (res * x) % mod;
    x = (x * x) % mod;
    n >>= 1;
  }
  return res;
}

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

  ll x, a;
  cin >> x >> a;

  cout << ((x < a) ? 0 : 10) << en;

  return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int N=202202;
int a[N];
ll pw[N],ans=0;
int n;
int main(){
	ll ans=0;
	scanf("%d",&n);
	pw[0]=1;	for (int i=1; i<=9; i++)	pw[i]=pw[i-1]*10;
	for (int i=1; i<=n; i++){
		int y=i%10,x=i,len=1;
		ll sum=0;
		for (; x>=10; x/=10)	len++;
		if (y==0)	continue;
		if (len==1){
			ans++;
			continue;	
		}
		if (x==y){
			sum+=2;
			if (len==2){
				ans+=3;
				continue;
			}
			int s=i/10;
			for (int j=2; j<len; j++)
				sum+=1ll*pw[j-2]*(s%10)*2,s/=10;
			sum+=2;
			sum--;
		}
		if (x>y)	sum+=1ll*pw[len-2]*2;
		for (int j=0; j<len-2; j++)	sum+=pw[j]*2;
		ans+=sum;
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 128
#k = int(input())
#s = input()
#a, b = map(int, input().split())
#s, t = map(str, input().split())
#l = list(map(int, input().split()))
#l = [list(map(int,input().split())) for i in range(n)]
#a = [list(input()) for _ in range(n)]

a,b,c = map(int, input().split())

if (b - a == c - b):
    print("YES")
else:
    print("NO")


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

void swap(int a,int b){
    int tmp;
    if(a<b){
        tmp = a;
        a = b;
        b = tmp;
    }
}

int gcddi(int a, int b){
    swap(a,b);
    // printf("swap");
    int r;
    r = a%b;

    while(r != 0){
        // printf("%d\n",r);
        a = b;
        b = r;
        r = a%b;
    }
    return b;
}

int gcdtri(int a,int b, int c){
    int former = gcddi(a,b);
    // printf("gcdtri");

    return gcddi(former,c);
}


int main(void){
    int k,i,j,l;
    long int sum = 0;

    scanf("%d",&k);
    for(i=1;i<=k;i++){
        for(j=1;j<=k;j++){
            for(l=1;l<=k;l++){
                sum += gcdtri(i,j,l);
            }
        }
    }

    printf("%ld",sum);
    return 0;
}

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

class quick_find {
	vector<int> rt;
public:
	vector<vector<int>> vs;
	quick_find(int n) : rt(n), vs(n) {
		for (int i = 0; i < n; i++) rt[i] = i, vs[i].push_back(i);
	}
	int find(int a) {
		return rt[a];
	}
	bool same(int a, int b) {
		return rt[a] == rt[b];
	}
	void unite(int a, int b) {
		a = rt[a], b = rt[b];
		if (a == b) return;
		if (vs[a].size() < vs[b].size()) swap(a, b);
		for (auto& v : vs[b]) rt[v] = a;
		copy(vs[b].begin(), vs[b].end(), back_inserter(vs[a]));
	}
	int size(int a) {
		return vs[rt[a]].size();
	}
};

int main()
{
	int H, W;
	cin >> H >> W;
	vector<string> S(H);
	for (int i = 0; i < H; i++) {
		cin >> S[i];
	}
	quick_find uf(H * W);
	quick_find uf2(H * W * 2);
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (i + 1 < H && S[i + 1][j] != S[i][j]) {
				uf.unite(i * W + j, (i + 1) * W + j);
				uf2.unite(H * W + i * W + j, (i + 1) * W + j);
				uf2.unite(i * W + j, H * W + (i + 1) * W + j);
			}
			if (j + 1 < W && S[i][j + 1] != S[i][j]) {
				uf.unite(i * W + j, i * W + j + 1);
				uf2.unite(H * W + i * W + j, i * W + j + 1);
				uf2.unite(i * W + j, H * W + i * W + j + 1);
			}
		}
	}
	ll res = 0;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) if (uf.find(i * W + j) == i * W + j) {
			ll c1 = 0, c2 = 0;
			for (auto v : uf.vs[i * W + j]) {
				(uf2.same(i * W + j, v) ? c1 : c2) += 1;
			}
			res += c1 * c2;
		}
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 32640
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <stdio.h>
#include <cmath>
#include <math.h>
#include <sstream>
#include <iomanip>
#include <time.h>
#include <fstream>
#include <map>

using namespace std;

int main(){
	int r;
	cin>>r;
	if (r<1200){
		cout<<"ABC"<<endl;
		return 0;
	}
	if (r<2800){
		cout<<"ARC"<<endl;
		return 0;
	}
	cout<<"AGC"<<endl;	
	return 0;
}


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

#define fastio 			ios::sync_with_stdio(0);	cin.tie(0); cout.tie(0);  cout<<fixed;  cout<<setprecision(12);
#define randomINT 		mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define	newl 			cout<<"\n"
#define DISP(as)		for(auto it : as) cout<<it<<" ";newl;
#define all(x)         	(x).begin(),(x).end()
#define mset(x,val)    	memset(x,val,sizeof(x))
#define newl           	cout<<"\n"
#define pb             	push_back
#define mp             	make_pair
#define f 				first
#define s 				second
#define dline          cerr<<"///REACHED///\n";
#define deb1(x)        cerr<<#x<<" = "<<x<<'\n';
#define deb2(x,y)      cerr<<'['<<#x<<','<<#y<<"] = "<<'['<<x<<','<<y<<']'<<'\n';
#define deb3(x,y,z)    cerr<<'['<<#x<<','<<#y<<','<<#z<<"] = "<<'['<<x<<','<<y<<','<<z<<']'<<'\n';

typedef long long 				ll;
typedef long double 			ld;
typedef vector<ll> 				vll;
typedef pair<ll , ll> 			pll;
typedef pair<ld, ld> 			pld;
typedef unordered_map<ll, ll> 	um;
typedef vector<pll> 			vpll;

const ll 	MAX5 	= 	1e+5 + 7;
const ll 	MAX7 	= 	1e+7 + 7;
const ll 	MAXN 	= 	MAX7;
const ll   	INF   	=  	0x7f7f7f7f7f7f7f7f;
const int  	INFi 	=  	0x7f7f7f7f;
const ll 	MOD		=  	1e+9 + 7;

const ll N = 3*MAX5;
// <------------- Declare Variables Here ------------> //

ll T = 1;
ll n, x, m, y, k, z, l;
string s, t, d, c;

vll color, adj[N];
map<pll,ll> a;
// <------------- Implement Functions Here ----------> //

void dfs(ll x, ll p, ll d = 0) {
	color[x] = (d&1);
	for(auto it : adj[x]) {
		if(it != p) {
			dfs(it, x , d^a[{x,it}]);
		}
	}	
}

// <------------- Start of main() -------------------> //

void MAIN() {
	cin >> n;
	color = vll(n+1);
	for(ll i=1;i<n;i++) {
		cin>>x>>y>>z;
		adj[x].pb(y);
		adj[y].pb(x);
		a[{x,y}] = z;
		a[{y,x}] = z;
	}

	dfs(1,-1);

	for(ll i=1;i<=n;i++) cout<<color[i]<<"\n";
}

int main() {
	fastio; randomINT;
	//cin >> T;
	while (T--) {
		MAIN();
	}
	return 0;
}


Measured memory_bytes: 31632
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
using ll=long long;
using vec=vector<ll>;
using graph = vector<vector<ll>>;
#define loop(i,n) for(ll i=0;i<n;i++)
#define Loop(i, m, n) for(ll i = m;i < n;i++)
#define pool(i,n) for(ll i=n-1;i>=0;i--)
#define Pool(i, m, n) for(ll i=n-1;i>=m;i--)
#define MAX 999999999ll
#define MIN -999999999ll
#define setbit bitset<8>
#define flagcount __builtin_popcount
#define flag(x) (1<<x)
#define flagadd(bit,x) bit|=flag(x)
#define flagpop(bit,x) bit&=~flag(x) 
#define flagon(bit,i) bit&flag(i)
#define flagoff(bit,i) !(bit & (1<<i))
int main() {
  ll n;
  string s;
  cin>>n>>s;
  ll ans=1;
  if(n==1){
    cout<<1;
  }
  else{
  loop(i,n-1){
    if(s.at(i)!=s.at(i+1)){
      ans++;
    }
  }

  cout<<ans;
  }
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define mod 1000000007
#define INF 2147483647
#define fi first
#define se second
int abs(int a,int b){
  int c=max(a,b)-min(a,b);
  return c;
}
int gcd(int a,int b){
  int c=a%b;
  while(true){
    if(c==0) break;
    a=b;
    b=c;
    c=a%b;
  }
  return b;
}
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a,b,d=0;
  int c[1000000];
  cin>>a>>b;
  for(int i=0;i<a;i++) cin>>c[i];
  sort(c,c+a,greater<int>());
  for(int i=0;i<a;i++){
    if(c[i]>=b)  d++;
    else break;
  }
  cout<<d<<"\n";
}


Measured memory_bytes: 2432
#include <stdio.h>
 
int dayOfWeek(int year, int month, int day)
{
    if (month == 1 || month == 2) {
        year--;
        month += 12;
    }
    return (year + year / 4 - year / 100 + year / 400
        + (13 * month + 8) / 5 + day) % 7;
}
 
int main()
{
    int m, d;
    char *day[7] = {
        "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"
    };
     
    while (1) {
        scanf("%d%d", &m, &d);
        if (m == 0 || d == 0) break;
        puts(day[dayOfWeek(2004, m, d)]);
    }
    return 0;
}



Measured memory_bytes: 2112
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC114A
{
    class Program
    {
        static void Main(string[] args)
        {
            int x = int.Parse(Console.ReadLine());

            if (x == 7 || x == 5 || x == 3)
            
                Console.WriteLine("YES");

                else
                Console.WriteLine("NO");

                Console.ReadKey();
            
           

          
        }
    }
}

Measured memory_bytes: 11092
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	if(n%1000==0)
	{
		cout<<0<<endl;
	}
	else if(n<1000)
	{
		cout<<1000-n<<endl;
	}
	else
	{
		int a = n%1000;
		cout<<1000-a<<endl;
	}
}

Measured memory_bytes: 3632
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    String readValue;
    while ((readValue = reader.readLine()) != null) {
      int h = Integer.parseInt(readValue.split(" ")[0]);
      int w = Integer.parseInt(readValue.split(" ")[1]);
      if (h == 0 && w == 0)
        break;
      for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
          System.out.print((i % 2 == 0 && j % 2 == 0) || (i % 2 == 1 && j % 2 == 1) ? "#" : ".");
        }
        System.out.println();
      }
      System.out.println();
    }
  }

}

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

int main(){
  long long A,B,C,K,ans=0;
  cin>>A>>B>>C>>K;
  
  while(K){
    if(A!=0){
      A--; ans++; K--;
    }else if(B!=0){
      B--; K--;
    }else{
      ans-=K;
      K=0;
    }
  }
  cout<<ans;
}
    

Measured memory_bytes: 3636
def cumsum(T, K):
    R = [[0] * K for _ in range(K)]
    for i in range(K):
        t = 0
        for j in range(K):
            t += T[i][j]
            R[i][j] = t
    for i in range(K):
        t = 0
        for j in range(K):
            t += R[j][i]
            R[j][i] = t
    return R

def fm(B, W, K):
    m = 0
    for i in range(K):
        for j in range(K):
            t = B[i][j]
            if i == K - 1 or j == K - 1:
                t += W[K - 1][K - 1] - W[i][j]
            else:
                t += B[K - 1][K - 1] - B[K - 1][j] - B[i][K - 1] + B[i][j]
                t += W[K - 1][j] + W[i][K - 1] - 2 * W[i][j]
            m = max(m, t)
    return m

def main():
    N, K = map(int, input().split())
    K2 = 2 * K
    B = [[0] * K for _ in range(K)]
    W = [[0] * K for _ in range(K)]
    for _ in range(N):
        x1, y1, c = input().split()
        x, y = int(x1) % K2, int(y1) % K2
        if c == 'B':
            x = (x - K) % K2
        if x >= K and y >= K:
            x, y = x - K, y - K
        if x < K and y < K:
            B[x][y] += 1
        else:
            x, y = (x - K, y) if y < K else (x, y - K)
            W[x][y] += 1
    B = cumsum(B, K)
    W = cumsum(W, K)
    return max(fm(B, W, K), fm(W, B, K))

print(main())


Measured memory_bytes: 82008
#include <stdio.h>
#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <set>
#include <algorithm>
#include <math.h>
using namespace std;
using i64 = int64_t;
#define rep(i, n) for(int i=0;i<n;++i)
#define rep2(i, x, n) for(int i=x;i<n;++i)

int main()
{   
    int a,b;
    cin >> a >> b;
    int c = a + b + int((a+b)%2==1);
    cout << c/2 << endl;
    return 0;
}

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

using namespace std;
typedef long long ll;
typedef pair<int, int> pair2;
typedef pair<int, pair<int, int> > pair3;
typedef pair<int, pair<int, pair<int, int> > > pair4;
#define MAXN 200013
#define INF 1000000000000000000LL
#define MOD 1000000007LL
#define IINF 1000000000
#define mp make_pair
#define pb push_back
#define remove pop
#define all(x) x.begin(), x.end()

int values[MAXN];

int main() {
	if (fopen("FILENAME.in", "r")) {
		freopen("FILENAME.in", "r", stdin);
		freopen("FILENAME.out", "w", stdout);
	}
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);

	int n;
	string s;

	cin >> n >> s;

	vector<char> stacc;


	for (int i = 0; i < n; i++) {
		if (stacc.size() > 0 && stacc[stacc.size() - 1] == s[i]) {
			//Do nothing
		} else {
			stacc.push_back(s[i]);
		}
	}

	cout << stacc.size() << endl;
}

//GCD GCD GCD USE GCD IN MATH


Measured memory_bytes: 592
#include <stdio.h>
main()
{
  int a,b;
  char op;
  while(1){ 
     scanf("%d %c %d",&a, &op, &b);
    if ( op =='+' ){
      printf("%d\n",a+b);
    } else if ( op =='-' ){
      printf("%d\n",a-b);
    } else if ( op =='*'){
      printf("%d\n",a*b);
    } else if ( op =='/'){
      printf("%d\n",a/b);
    } else if( op == '?')
      break ;}
  return 0;
}

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

int main() {
  int n; ll k;
  cin >> n >> k;
  vector<int> a(n);
  for (int i=0;i<n;i++){
      cin >> a.at(i);
  }

  vector<int> s;
  vector<int> ord(n+1,-1);
  int c = 1;
  int l = 0;
  {
    int v = 1;
    while (ord[v] == -1) {
      ord[v] = s.size();
      s.push_back(v);
      v = a[v-1];
    }
    c = s.size() - ord[v];
    l = ord[v];
  }

  if (k < l) cout << s[k] << endl;
  else {
    k -= l;
    k %= c;
    cout << s[l+k] << endl;
  }
  return 0;
}


Measured memory_bytes: 5808
import sys

H, W = map(int, input().split())

if H % 3 == 0 or W % 3 == 0:
	print(0)
	sys.exit()

kai_1 = min(H,W)

def solve_2(a,b):
	w = a // 2
	s_l = (a-w) * b
	s_s = w * b
	s_r = 0

	tmp = s_l

	for i in range(b):
		s_r += a
		s_s -= w
		s_l -= (a-w)

		sa = max(s_r,s_s,s_l) - min(s_r,s_s,s_l)

		if tmp > sa:
			tmp = sa
			continue
		else:
			return tmp

kai_2 = solve_2(H,W)
kai_3 = solve_2(W,H)

print(min(kai_1,kai_2,kai_3))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
 
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll k;
  cin>>k;
  ll a,b;
  cin>>a>>b;
  for(ll i=a;i<=b;i++)
  {
      if(i%k==0)
      {
          cout<<"OK\n";
          return 0;
      }
  }
  cout<<"NG\n";
   
   
  return 0;
}

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

int main(void){
  int n, t;
  cin >> n >> t;

  long long int input;
  long long int sum = 0, nowend = -t;
  for(int i = 0; i < n; i++){
    cin >> input;
    if(input >= nowend){ sum += t; }
    else{ sum += (input + t - nowend); }
    nowend = input + t;
  }

  cout << sum << endl;
  
  return 0;
}


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

double dp[3100][3100];

int main() {
    int N;
    cin >> N;
    vector<double> p(N);
    for (int i = 0; i < N; i++) {
        cin >> p[i];
    }
    dp[0][0] = 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= i; j++) {
            dp[i + 1][j + 1] += dp[i][j] * p[i];
            dp[i + 1][j] += dp[i][j] * (1 - p[i]);
        }
    }

    double ans = 0;
    for (int i = N; i > N / 2; i--) {
        ans += dp[N][i];
    }
    printf("%.10f\n", ans);
}


Measured memory_bytes: 72448
n, k = map(int, input().split())
positions = [int(i) for i in input().split()]
scores = [int(i) for i in input().split()]
if max(scores) <= 0:
  print(max(scores))
else:
  positions = [0] + positions
  scores = [0] + scores
  max_point = -pow(10, 9)
  #print(max_point)
  dic = {}
  for i in range(1, n + 1):
    f_pos = i
    #print('f_pos',f_pos)
    if f_pos not in dic:
      point_loop = 0
      loop = 0
      pos_set = set([f_pos])
      while True:
        f_pos = positions[f_pos]
        point_loop += scores[f_pos]
        #print('pos', f_pos)
        #print(point)
        loop += 1
        if f_pos in pos_set:
          for j in pos_set:
            dic[j] = [loop, point_loop]
          break
        pos_set.add(f_pos)
    else:
      loop, point_loop = dic[f_pos]
    #print(loop, point)
    loop_c = k // loop
    r = k % loop
    if loop_c == 0 or point_loop <= 0:
      if point_loop <= 0:
        if loop_c > 0:
          r = loop
      point = 0
      for _ in range(r):
        f_pos = positions[f_pos]
        point += scores[f_pos]
        max_point = max(max_point, point)
    else:
      point1, point2 = 0, 0
      point1 = loop_c * point_loop
      max_point1 = point1
      for _ in range(r):
        f_pos = positions[f_pos]
        point1 += scores[f_pos]
        max_point1 = max(point1, max_point1)
      f_pos = i
      point2 = (loop_c - 1) * point_loop
      max_point2 = point2
      for _ in range(loop):
        f_pos = positions[f_pos]
        point2 += scores[f_pos]
        max_point2 = max(point2, max_point2)
      max_point = max(max_point, max(max_point1, max_point2))
  print(max_point)


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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

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

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
  for(auto &e:u) fill_v<T>(e,v...);
}

struct Music {
    int64 A, W, R, T;
    Music() {}
    Music(int64 A_, int64 W_, int64 R_, int64 T_) :A(A_), W(W_), R(R_), T(T_) {}

    bool operator<(const Music& rhs) const {
        return R+T > rhs.R+rhs.T;
    }
  };

int main(void) {
    int64 N;
    cin >> N;
    auto dp = make_v<int64>(4040, 2);
    fill_v<int64>(dp, -INF_LL);
    dp[4039][0] = 0;
    vector<Music> m(N);
    REP(i, N) {
        cin >> m[i].R >> m[i].A >> m[i].W >> m[i].T;
    }
    sort(all(m));
    int64 res = 0;
    REP(i, N) {
        auto dp2 = make_v<int64>(4040, 2);
        fill_v<int64>(dp2, -INF_LL);
        REP(k, 2) {
            for (int64 j = 4039; j >= 0; j--) {
                int64 rest = j-m[i].R;
//                if (dp[j][k] == -INF_LL) continue;
                chmax(dp2[j][0], dp[j][k]);
                if (rest <= 0) continue;
                chmin(rest, m[i].T);
                if (k == 0) {
                    chmax(dp[rest][1], dp[j][0]+m[i].A);
                    chmax(dp2[rest][0], dp[j][0]+m[i].A);
                } else {
                    chmax(dp[rest][1], dp[j][1]+m[i].W);
                    chmax(dp2[rest][0], dp[j][1]+m[i].W);
                }
            }
        }
        swap(dp, dp2);
    }
    REP(j, dp.size()) {
        REP(k, dp[j].size()) {
            chmax(res, dp[j][k]);
        }
    }
    cout << res << endl;
}



Measured memory_bytes: 3428
using System;
using System.Linq;
using System.Collections.Generic;

namespace b
{
    class Program
    {
        static void Main(string[] args)
        {
            var _  = Console.ReadLine().Split();
            var n = int.Parse(_[0]);
            var d = int.Parse(_[1]);

            var l = new List<int[]>();
            for(var i = 0; i < n; i++){
                var ary = Console.ReadLine().Split().Select(t => int.Parse(t)).ToArray();
                l.Add(ary);
            }

            var count = 0;
            for(var i = 0; i < n - 1; i++){
                for(var j = i + 1; j < n; j++){
                    var y = l[i];
                    var z = l[j];
                    var distance = 0.0;
                    for(var k = 0; k < d; k++){
                        distance += ((y[k] - z[k]) * (y[k] - z[k]));
                    }
                    distance = Math.Sqrt(distance);
                    
                    if(distance - Math.Floor(distance) == 0){
                        count++;
                    }
                }
            }

            Console.WriteLine(count);
        }
    }
}


Measured memory_bytes: 13396
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,a = 0, count = 0;
cin >> n;
vector<int> stories(n);
for(int i = 0; i < n; i++){
    cin >> stories[i];
}
for(int i = 0; i < n - 1; i++){
    if(stories[i] >= stories[i + 1]){
    if(i < n - 2) count++;
    if(i == n - 2){
        count++;
        a = max(count, a);
    }
}
    if(stories[i] < stories[i + 1])
    {
      a = max(a, count); 
      count = 0;
    }
}

cout << a << endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <time.h>
#include <list>

using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define reps(x,c) for(auto x:c)
#define all(x) begin(x), end(x)
#define pb(a) emplace_back(a) 
#define mp(a,b) make_pair((a),(b))
#define pl pair<ll,ll>
#define INF 2147483600
#define MOD 1000000007
#define fi first
#define se second
#define dbg(x) cout << #x"="<< (x) << endl
#define dbgv(x) cout<<#x<<endl;reps(y,x){cout<<y<<" ";}cout<<endl

int main(){
  ll a,b,c,x,y;cin>>a>>b>>c>>x>>y;
  ll ans=0,ans2=INF;
  ll minn=min(x,y);
  ll maxn=max(x,y);
  if(a+b>2*c){
  	ans+=minn*2*c;
  	x-=minn;
  	y-=minn;
  	ans2=maxn*2*c;
  }
  ans+=x*a;
  ans+=y*b;
  cout<<min(ans,ans2)<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<time.h>
#define pi acos(-1.0)
using namespace std;
int main()
{
//	long long begin_time=clock();
//	int t;
//	scanf("%d",&t);
//	while(t--)
//	{
		int n,i,j,flag=0,x,y=0,ma=0,mi=0x3f3f3f3f;
		char s[105];
	//	int a[],b[];
    	scanf("%d",&n);
	    scanf("%s",s);
	    x=strlen(s);
	    if(x<=n)
	    printf("%s\n",s);
	    else
	    {
	    	for(i=0;i<n;i++)
	    	printf("%c",s[i]);
	    	printf("...\n");
		}
//	}
//	long long end_time=clock();
//	printf("time=%lldms\n",end_time-begin_time);
}


Measured memory_bytes: 3696
from collections import Counter

n, m = map(int, input().split())
A = [int(i) for i in input().split()]

A[0] %= m
for i in range(n-1):
    A[i+1] += A[i]
    A[i+1] %= m
    
C = Counter(A)
ans = 0
for k, v in C.items():
    if k == 0:
        ans += v
    if v >= 2:
        ans += (v * (v-1)) // 2
        
print(ans)

Measured memory_bytes: 14636
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
#include <tuple>
#include <numeric>
#include <assert.h>
#include <functional>
#include <unordered_map>

using namespace std;

/*-----------------------------------------------------------------------------
　定義
 -------------------------------------------------------------------------------*/
#define ALL(a)			a.begin(), a.end()
#define REP(i, n)		for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n)	for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define INF				2e9
#define MOD				(1000 * 1000 * 1000 + 7)
#define Ceil(x, n)		(((((x))+((n)-1))/n))		/* Nの倍数に切り上げ割り算 */
#define CeilN(x, n)		(((((x))+((n)-1))/n)*n)		/* Nの倍数に切り上げ */
#define FloorN(x, n)	((x)-(x)%(n))				/* Nの倍数に切り下げ */
#define IsOdd(x)		(((x)&0x01UL) == 0x01UL)			
#define IsEven(x)		(!IsOdd((x)))						
#define	MAX_QWORD		((QWORD)0xFFFFFFFFFFFFFFFF)
#define M_PI			3.14159265358979323846
typedef long long		ll;
typedef pair<int, int>	P;

/*-----------------------------------------------------------------------------
　処理
 -------------------------------------------------------------------------------*/
// メイン
int main()
{
	int N, A;
	cin >> N >> A;
	int amari = N % 500;
	string ans = amari <= A ? "Yes" : "No";
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
N = gets.chomp.to_i
s = []
ab = 0
a = 0
b = 0
ba = 0

i = 0
while i < N
  s = gets.chomp
  if s[0] == "B"
    if s[s.size-1] == "A"
      ba += 1
    else
      b += 1
    end
  elsif s[s.size-1] == "A"
    a += 1
  end
  for x in 0...s.size-1
    if s[x] == "A"
      if s[x+1] == "B"
        ab += 1
      end
    end
  end
  i += 1
end

aorb = 0
if a < b
  aorb = a
else
  aorb = b
end
if a==0 && b==0 && ba>0
  ba -= 1
end

answer = ab + ba + aorb

puts answer

Measured memory_bytes: 3836
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <iomanip>
#include <functional>
#include <bitset>
#include <limits>
#include <cstdio>
#include <cmath>
#include <cassert>
#include <random>

#ifdef DEBUG
#include "library/Utility/debug.cpp"
#else
#define debug(...)
#endif

#define rep(i,n) for(int i=0;i<(n);++i)
#define EL '\n'
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
using lnt = long long;
struct FIO{FIO(){std::cin.tie(0);std::cout.tie(0);std::ios_base::sync_with_stdio(0);std::cout<<std::fixed<<std::setprecision(15);}}fIO;
/*-*/

int main() {
	int x;
	std::cin >> x;
	if(x>=30) print("Yes");
	else print("No");
}


Measured memory_bytes: 3648
x, n = map(int, input().split())
if n == 0:
    print(x)
else:
    p = list(map(int, input().split()))
    p.sort()
    mi = 101
    chk = [1 for i in range(0, 102)]
    for i in range(n):
        chk[p[i]] = 0

    for i in range(0, 102):
        if chk[i] == 1:
            if abs(i - x) < mi:
                mi = abs(i - x)
                ans = i
    print(ans)

Measured memory_bytes: 61788
#include <iostream>
#include <iomanip>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <regex>
using namespace std;
using pii  = pair<int,int>;
using ll=long long;
using ld=long double;
#define pb push_back
#define mp make_pair
#define stpr setprecision
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define rep(i,n) for(ll i=0;i<(n);++i)
#define Rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define rRep(i,a,b) for(int i=a;i>=b;i--)
#define crep(i) for(char i='a';i<='z';++i)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define ALL(x) (x).begin(),(x).end()
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define endl '\n'
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b, a%b));}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
constexpr ll MOD=1000000007;
constexpr ll INF=1000000011;
constexpr ll MOD2=998244353;
constexpr ll LINF = 1001002003004005006ll;
constexpr ld EPS=10e-8;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename T> istream& operator>>(istream& is,vector<T>& v){for(auto&& x:v)is >> x;return is;}
template<typename T,typename U> istream& operator>>(istream& is, pair<T,U>& p){ is >> p.first; is >> p.second; return is;}
template<typename T,typename U> ostream& operator>>(ostream& os, const pair<T,U>& p){ os << p.first << ' ' << p.second; return os;}
template<class T> ostream& operator<<(ostream& os, vector<T>& v){
    for(auto i=begin(v); i != end(v); ++i){
        if(i !=begin(v)) os << ' ';
        os << *i;
    }
    return os;
}

  ll N,K,A[200007],F[200007];
  pair<ll,ll> P[200007];

bool chek(ll key){
  ll sum=0;
  rep(i,N){
    if(P[i].first>key){
      sum+=P[i].second-(key/(P[i].first/P[i].second));
    }
    if(sum>K){
      return 1;
    }
  }
  return 0;
}

int main(){
  ll s=0;
  cin >> N >> K;
  rep(i,N){
    cin >> A[i];
    s+=A[i];
  }
  rep(i,N){
    cin >> F[i];
  }
  if(s<=K){
    cout << 0 << endl;
    return 0;
  }
  sort(A,A+N);
  sort(F,F+N);
  rep(i,N){
    P[i]=(mp(A[i]*F[N-i-1],A[i]));
  }
  ll ng=2*10e11,ok=0;
  while(ng-ok>1){
        ll mid = (ok+ng)/2;
        if(chek(mid)){
            ok = mid;
        }
        else{
            ng = mid;
        }
    }
  cout << ok+1 << endl;
}

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

using namespace std; 
#define REP(i, n) for (int i = 0; i < (n); i++)

typedef long long ll;

int main(int argc, char const *argv[])
{
    cin.tie(0);
   	ios::sync_with_stdio(false);
    ll N, X; cin >> N >> X;
    vector<ll> v(200001);
    vector<ll> s(200001);
    s[0] = 0LL;
    for (ll i = 1LL; i <= N; i++) {
        cin >> v[i];
        s[i] = v[i] + s[i - 1LL];
    }
    ll res = LLONG_MAX;
    for (ll i = 1LL; i <= N; i++) {
        ll energy = LLONG_MIN + i * X;
        for (ll j = 0; j < N/i + 1; j++) {
            ll S = s[N - j * i] - s[max(N - (j + 1) * i, 0LL)];
            if(j == 0LL) energy += 5LL * S;
            else energy += (2LL*j + 3LL) * S;
        } 
        res = min(res, energy);
    }
    res += N * X + LLONG_MIN;
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 3456
n = int(input())
a = [int(x) for x in input().split()]
z = 0
z_old = 0
x = a[0]
for i in range(1,n):
  if a[i] > x:
    if z > z_old:
    	z_old = z
    z = 0
  else:
    z += 1
  x = a[i]
print(max(z, z_old))

Measured memory_bytes: 14224
#include <iostream>
#include <chrono>
#include <cmath>
#include <string.h>
#include <iomanip>

#define MAX(a, b) a > b ? a : b

using namespace std;

int L;
double res;

int main()
{
	cin >> L;

	res = (double)L * L * L;
	res /= 27;

	cout << fixed;
	cout << setprecision(6) << res << '\n';
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x)
#define show(obj) {for(auto x:obj)cout<<x<<' ';cout<<endl;}
#define line "----------"
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
const int inf = 1001001000;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
	ll n,m; cin>>n>>m;
	string s,t; cin>>s>>t;
	ll g = n*m/__gcd(n,m);
	map<ll,char> check;
	// cout<<g<<endl;
	rep(i,n){
		ll pos = g/n * (ll)i;
		check[pos] = s[i];
	}
	rep(i,m){
		ll pos = g/m * (ll)i;
		if(check.count(pos) != 0){
			if(check[pos] != t[i]){
				cout<<-1<<endl; return 0;
			}
		}
	}
	cout<<g<<endl;
	return 0;
}

Measured memory_bytes: 6144
import java.util.*;
public class Main{
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
      int a = sc.nextInt();
      int b = sc.nextInt();
      int c = sc.nextInt();
      for(int i = 1;i <= b;i++){
      	if((a*i)%b==c){
        	System.out.println("YES");
          return;
        }
      }
      System.out.println("NO");
    }
}


Measured memory_bytes: 23636
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;

namespace AtCoder_Beginner_Contest_131
{
    //解説動画参照(https://www.youtube.com/watch?v=XI8exXVxZ-Q)
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        
        const int V = 100005;
        static List<long>[] to = new List<long>[V * 2];
        static bool[] visited = new bool[V * 2];
        static long[] cnt;
        static void dfs(long v)
        {
            if (visited[v]) return;
            visited[v] = true;
            cnt[v / V]++;
            foreach (var u in to[v])
            { dfs(u); }
        }
        static void Main(string[] args)
        {
            for(var i=0;i<V*2; ++i)
            {
                to[i] = new List<long>();
            }
            var N = Sarray()[0];
            for(var i=0;i<N;++i)
            {
                var xy = Sarray();
                var x = xy[0];
                var y = xy[1];
                y += V;
                to[x].Add(y);
                to[y].Add(x);
            }
            var ans = 0L;
            for (var i = 0; i < V * 2; ++i)
            {
                if (visited[i]) continue;
                cnt = new long[2];
                dfs(i);
                ans += cnt[0] * cnt[1];
            }
            WriteLine(ans - N);
        }
    }
}

Measured memory_bytes: 44500
N = int(input())
a = N // 100
b = (N - 100 * a) // 10
c = (N - 100 * a - b * 10 )
if a == 7 :
    print('Yes')
elif b == 7 :
    print('Yes')
elif c == 7 :
    print('Yes')
else :
    print('No')


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

int main(){
	ios_base::sync_with_stdio(0);
  	cin.tie(NULL);cout.tie(NULL); cerr.tie(NULL); 
  	#ifdef LOCAL
  		freopen("in.txt", "r", stdin);
  		freopen("out.txt", "w", stdout);
  	#endif
  	
  	long long n,m;
  	cin >> n >> m;
  	long long arr[n+1];
  	long long sum = 0;

  	for(int i = 1;i <= n;i++){
  		cin >> arr[i];
  		sum += arr[i];
  	}
  	long double x = sum * ((double)1 / (m*4));
  	long long cnt = 0;
  	for(long long i = 1;i <= n;i++){
  		if(arr[i] >= x) cnt++;
  	}
  	cout << (cnt >= m ? "Yes" : "No");

}

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

using namespace std;
using ll = long long;

int main()
{
  int a,b,c;
  int v1[3][3];
  for (size_t i = 0; i < 3; i++) {
    for (size_t j = 0; j < 3; j++) {
      cin >> a;
      v1[i][j] = a;
    }
  }
  cin >> b;
  while (b--) {
    cin >> a;
    for (size_t i = 0; i < 3; i++) {
      for (size_t j = 0; j < 3; j++) {
        if (a == v1[i][j]) {
          v1[i][j] = 0;
        }
      }
    }
  }
  for (size_t i = 0; i < 3; i++) {
    c = 0;
    for (size_t j = 0; j < 3; j++) {
      c+= v1[i][j];
    }
    if (c == 0) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  for (size_t j = 0; j < 3; j++) {
    c = 0;
    for (size_t i = 0; i < 3; i++) {
      c+= v1[i][j];
    }
    if (c == 0) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  if ((v1[0][0] + v1[1][1] + v1[2][2]) == 0) {
    cout << "Yes" << endl;
    return 0;
  }
  if ((v1[0][2] + v1[1][1] + v1[2][0]) == 0) {
    cout << "Yes" << endl;
    return 0;
  }


  cout << "No" << endl;


  return 0;
}


Measured memory_bytes: 3556
def main():
    H,W = map(int, input().split())
    field = []
    for i in range(H):
        buf=list(input())
        field.append(buf)

    for i in range(H):
        for j in range(W):
            if field[i][j]=="#":
                continue
            num = 0
            for k in range(-1,2):
                for l in range(-1,2):
                    if i+k==-1 or i+k==H or j+l==-1 or j+l==W:
                        continue
                    if field[i+k][j+l]=="#":
                        num = num +1
            field[i][j]=str(num)
    
    for i in range(H):
        print("".join(field[i]))



        





main()

Measured memory_bytes: 3188
#include<bits/stdc++.h>
#define LLI long long int
#define ULTRA 2134567890
#define de(x) if(x==MODE && x!=0)

#define MODE 1

using namespace std;

int main()
{
    int i,j;
    int a,b;

    scanf("%d %d", &a, &b);

    if(1<=a && a<=9 && 1<=b && b<=9)
    {
        printf("%d\n", a*b);
    }
    else
    {
        printf("-1\n");
    }

    return 0;
}


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

struct Solver {
	void solve() {
		int N;
		cin >> N;

		set<string> prize;
		for( int i = 0; i < N; ++i ) {
			string s;
			cin >> s;
			prize.insert( s );
		}

		cout << prize.size() << endl;
	}
};

int main() {
	ios::sync_with_stdio( false );
	cout << fixed << setprecision( 10 );
	Solver().solve();

	return 0;
}


Measured memory_bytes: 19244
const MOD: u64 = 1000000007;

fn main() {
    let (h, w) = {
        let v = read_vec::<usize>();
        (v[0], v[1])
    };
    let maze: Vec<Vec<char>> = {
        let mut maze: Vec<Vec<char>> = Vec::new();
        for _ in 0..h {
            let s = read::<String>();
            maze.push(s.chars().collect::<Vec<_>>());
        }
        maze
    };
    let mut dp = vec![vec![0; w]; h];
    dp[0][0] = 1;

    for i in 0..h {
        for j in 0..w {
            if maze[i][j] == '#' {
                continue;
            }
            if i > 0 && maze[i-1][j] != '#' {
                let tmp = dp[i-1][j];
                add(&mut dp[i][j], tmp);
            }
            if j > 0 && maze[i][j-1] != '#' {
                let tmp = dp[i][j-1];
                add(&mut dp[i][j], tmp);
            }
        }
    }

    println!("{}", dp[h-1][w-1]);
}

fn add(a: &mut u64, b: u64) {
    if *a + b >= MOD {
        *a = *a + b - MOD;
    } else {
        *a = *a + b;
    }
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}


Measured memory_bytes: 16636
#include<stdio.h>

int main(void){
int a,b,c,x,y,z;
scanf("%d%d%d",&a,&b,&c);

if(a>=b){
x=a;
a=b;
b=x;
} 
if(b>=c){
y=b;
b=c;
c=y;
}
if(a>=b){
z=a;
a=b;
b=z;
}
printf("%d %d %d\n",a,b,c);
return 0;
}

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

int main() {
    ll n,ans=0,r[4000]={-1},g[4000]={-1},b[8000]={0},rn=0,gn=0,bn=0,no=0;
    string s;
    cin >> n >> s;
    for(ll i=0;i<n;i++){
        if(s[i]=='R'){
            r[rn]=i;
            rn++;
        }else if(s[i]=='G'){
            g[gn]=i;
            gn++;
        }else if(s[i] =='B'){
            b[i]=1;
            bn++;
        }
    }
    for(ll i=0;i<rn;i++){
        for(ll j=0;j<gn;j++){
            ll hogea = max(r[i],g[j]),hogeb = min(r[i],g[j]);
            ll hoge = hogea - hogeb;
            if(b[hogea + hoge])no++;
            if(hoge%2==0 && b[hogeb + hoge/2])no++;
            if(hogeb - hoge >= 0 && b[hogeb - hoge])no++;
        }
    }
    ans = rn*gn*bn - no;
    cout << ans << endl;
}

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

int main(){
    int n;
    long long int k;
    scanf("%d %lld",&n,&k);
    map<int,long long int> mp;
    for(int i=0;i<n;++i){
        int a,b;
        scanf("%d %d",&a,&b);
        mp[a] += b;
    }
    long long int cnt=0;
    for(int i=1;i<=100000;++i){
        cnt += mp[i];
        if(cnt >= k){
            printf("%d\n",i);
            break;
        }
    }

    return 0;
}


Measured memory_bytes: 6528
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
int main(void){
    int x,a,b; cin>>x>>a>>b;
    if(a>=b){
        cout<<"delicious"<<endl;
    }else if(x+a>=b){
        cout<<"safe"<<endl;
    }else{
        cout<<"dangerous"<<endl;
    }
    
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main () {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  int E = A + B;
  int F = C + D;
  if (E > F) {
    cout << "Left" << endl;
  } else if (E < F) {
    cout << "Right" << endl;
  } else {
    cout << "Balanced" << endl;
  }
}


Measured memory_bytes: 3644
// #include<bits/stdc++.h>
// using namespace std;
 
// const int N = 10000, MAXI = 10000;
 
// int main() {
//     freopen("output.txt", "r", stdin);
//     freopen("input.txt", "w", stdout);
//     srand(time(nullptr));
//     int tc = 10;
//     cout << tc << "\n";
//     while (tc--)
//     {
//         int n = rand()%N+1;
//         cout << n << " ";
//         cout << rand()%n + 1 << "\n";
//         for(int i=1;i<=n;i++)
//             cout << rand()%MAXI + 1 << " ";
//         cout << "\n";
//         cout << "~\n";
//     }
 
//     return 0;
// }
 
 
 
 
 
 
 
 
//---------------------------------------------//
 
 
 
 
 
 
 
 
 
 
//  /* while(!cin.eof()) */
 
#include<bits/stdc++.h>
using namespace std; 
#define int long long 
#define mod (int)(1e9+9)
#define endl '\n'
#define MAXI (int)(3e17+10)
#define N 100005
 
 
// Driver code to test above functions
int32_t main()
{
   
     
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
 
   	int n, m, x;
   	cin >> n >> m >> x;

   	int c[n];
   	int a[n][m];

   	for(int i=0;i<n;i++)
   	{
   		cin >> c[i];
   		for(int j=0;j<m;j++)
   			cin >> a[i][j];
   	}

   	//cout << "nfn";
   	int ans = MAXI;
   	for(int i=1;i<(1<<n);i++)
   	{
   		int k = i, j = 0;
   		vector<int> p(n, 0);
   		while(k)
   		{
   			p[j] = k%2;
   			k/=2;
   			j++;
   		}

   		//out << i << endl;
   		// if(i==6)
   		// {
   		// 	for(auto j:p)
   		// 		cout << j << endl;
   		// }

   		int algo[m] = {0}, mini = 0;
   		for(int j=0;j<n;j++)
   		{
   			if(p[j]==1){
   				for(int l=0;l<m;l++)
   					algo[l] += a[j][l];
   				mini += c[j];
   			}
   			
   		}



   		int flag = 1;
   		for(int j=0;j<m;j++)
   			if(algo[j]<x)
   				flag = 0;

   		if(flag==1)
   			ans = min(ans, mini);
   	}

   	if(ans==MAXI)
   		ans = -1;

   	cout << ans;

    return 0;
 
} 

Measured memory_bytes: 3652
#include <iostream>

using namespace std;

int main()
{
  int N;
  cin >> N;

  double sum = 0.0;
  for (int i = 0; i < N; i++) {
    string xs, us;
    cin >> xs >> us;

    if (us == "JPY")
      sum += (double)stoi(xs);
    else if (us == "BTC")
      sum += (double)(stod(xs) * 380000.0);
  }

  cout << sum << endl;

  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<numeric>
#include<algorithm>
#include<string>
#include<cmath>
#include<set>
#include<map>
#include<stack>
#include<queue>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;


int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int S;
	cin >> S;
	int h, m, s;
	h = S / 3600;
	m = (S % 3600) / 60;
	s = S % 60;
	cout << h << ":" << m << ":" << s << "\n";

	return 0;
}


Measured memory_bytes: 3156
// Created by Nandu Vinodan
#include <bits/stdc++.h>

#define db1(x) cout<<#x<<"="<<x<<'\n'
#define db2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define db3(x,y,z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'
#define rep(i,a,n) for(int i=a;i<=(n);++i)
#define repD(i,a,n) for(int i=a;i>=(n);--i)
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define vi vector<int>
#define pi pair<int, int>
#define INF INT_MAX
#define _INF INT_MIN
#define TC 0

using namespace std;
using ll = long long;

void testcase() {
    ll h, w; cin >> w >> h;

    if (h==1 || w==1) {
    	cout << "1\n";
    	return;
    }
    ll res = 0;

    ll r1 = (h+1)/2;
    ll r2 = h/2;

    res = (r1+r2) * (w/2);
    if (w & 1)
    	res += r1;

    cout << res << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    if (TC)
        cin>>t;
    while(t--) {
        testcase();
    }
    return 0;
}

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

#define IOS ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(0)
#define endl "\n"
#define int long long
typedef vector<int> vi;
#define all(x) x.begin(),x.end()
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
#define OO 1e9
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
typedef long long ll;
#define in_range(x, y, r, c) ((x >= 0 && x < r && y >= 0 && y < c))


const double eps=1e-9;
const int MOD=998244353;
const int N=(int)3*1e5+9;
const int inf = 1<<30;


template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
int est[N],west[N];
int n;
int32_t main() {
IOS;
int n,m;
cin>>n>>m;
int ans;
if(n>=2)n-=2;
if(m>=2)m-=2;
cout<<n*m;
}

Measured memory_bytes: 256
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        n: usize,
        l: [i64; n],
    }

    let mut cnt = 0;
    for i in 0..n {
        for j in (i + 1)..n {
            for k in (j + 1)..n {
                if l[i] == l[j] || l[j] == l[k] || l[k] == l[i] {
                    continue;
                }
                if l[i] + l[j] > l[k] && l[j] + l[k] > l[i] && l[k] + l[i] > l[j] {
                    cnt += 1;
                }
            }
        }
    }

    println!("{}", cnt);
}


Measured memory_bytes: 2172