akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
ll MOD = 1000000007;
ll INFL = 1ll << 60;
ll INF = 1 << 28;

ll n, q;
string s;
vector<pair<char, char> > v(200010);

// 落ちるかどうか判定。落ちない=0,左から落ちる=-1、右から=1
int ochi(int now) {
  for (int i = 0; i < q; i++) {
    if (s[now] == v[i].first) {
      if (v[i].second == 'R')
        now++;
      else
        now--;
    }
    if (now < 0) return -1;
    if (now >= n) return 1;
  }
  return 0;
}

// ====================================================================

int main() {
  cin >> n >> q;
  cin >> s;
  char t, d;
  for (int i = 0; i < q; i++) {
    cin >> v[i].first >> v[i].second;
  }

  // 左から落ちるやつの境界線を探る
  ll left = -1, right = n + 1;
  while (right - left > 1) {
    ll mid = (left + right) / 2;
    if (ochi(mid) == -1)
      left = mid;
    else
      right = mid;
  }
  ll hidari = right;

  left = -1;
  right = n + 1;
  while (right - left > 1) {
    ll mid = (left + right) / 2;
    if (ochi(mid) != 1)
      left = mid;
    else
      right = mid;
  }
  ll migi = right;

  cout << migi - hidari << endl;
}


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

using namespace std;

vector <vector <long long> > dp[4];
int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, 1, -1, 0};
vector <string> M;

int main()
{
	int H, W;
	cin >> H >> W;
	for (int i = 0; i < 4; i++){
		dp[i].resize(H);
		for (int j = 0; j < H; j++)
			dp[i][j].resize(W);
	}
	
	M.resize(H);
	for (int i=0;i<H;i++)
		cin>>M[i];
	
	for (int k=0;k<4;k++){
		if (dx[k]==-1){
			for (int i=0;i<H;i++){
				for (int j=0;j<W;j++){
					int x=i+dx[k],y=j+dy[k];
					if (x!=H && x!=-1 && y!=W && y!=-1 && M[i][j]=='.')
						dp[k][i][j] = dp[k][x][y] + 1;
					else if (M[i][j] == '.')
						dp[k][i][j] = 1;
				}
			}
		}
		
		else{
			if (dy[k] == -1)
				for (int i = 0; i < H; i++){
					for (int j = 0; j < W; j++){
						int x = i + dx[k], y = j + dy[k];
						if (x != H && x != -1 && y != W && y != -1 && M[i][j] == '.')
							dp[k][i][j] = dp[k][x][y] + 1;
						else if (M[i][j] == '.')
							dp[k][i][j] = 1;
					}
				}
				
			else{
				for (int i = H - 1; i >= 0; i--){
					for (int j = W - 1; j >= 0; j--){
						int x = i + dx[k], y = j + dy[k];
						if (x != H && x != -1 && y != W && y != -1 && M[i][j] == '.')
							dp[k][i][j] = dp[k][x][y] + 1;
						else if (M[i][j] == '.')
							dp[k][i][j] = 1;
					}
				}
			}
		}
	}
	
	long long ans = 0;
	for (int i = 0; i < H; i++)
		for (int j = 0; j < W; j++)
			ans = max(ans, dp[0][i][j] + dp[1][i][j] + dp[2][i][j] + dp[3][i][j] - 3);
	cout<<ans<<endl;
}

Measured memory_bytes: 129664
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define FORR(i, m, n) for (int i = (m); i >= (n); i--)
#define REP(i, n) FOR(i, 0, (n))
#define REPR(i, n) FORR(i, (n) - 1, 0)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define REPS(c, s) for (char c : s)
#define ALL(c) (c).begin(), (c).end()
#define sz(v) (int)v.size()
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000001000000001LL;
const char EOL = '\n';
 
void solve();
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(numeric_limits<double>::max_digits10);
    solve();
    return 0;
}

void solve() {
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    REP(i, h) cin >> s[i];

    int ans = 0;
    REP(i, h) REP(j, w) {
        if (s[i][j] == '#') continue;
        vector<vector<int>> d(h, vector<int>(w, INF));
        d[i][j] = 0;
            deque<tuple<int, int, int>> q;
            q.emplace_back(i, j, 0);
            set<pair<int, int>> memo;
            memo.emplace(i, j);
            int r, c, t;
            while (!q.empty()) {
                tie(r, c, t) = q.front(); q.pop_front();
                // cout << r << ":" << c << "/" << t << EOL;
                d[r][c] = t;

                auto p = make_pair(r - 1, c);
                if (r != 0 && s[r - 1][c] != '#' && memo.count(p) == 0) {
                    memo.emplace(p);
                    q.emplace_back(r - 1, c, t + 1);
                }
                p = make_pair(r + 1, c);
                if (r != h - 1 && s[r + 1][c] != '#' && memo.count(p) == 0) {
                    memo.emplace(p);
                    q.emplace_back(r + 1, c, t + 1);
                }
                p = make_pair(r, c - 1);
                if (c != 0 && s[r][c - 1] != '#' && memo.count(p) == 0) {
                    memo.emplace(p);
                    q.emplace_back(r, c - 1, t + 1);
                }
                p = make_pair(r, c + 1);
                if (c != w - 1 && s[r][c + 1] != '#' && memo.count(p) == 0) {
                    memo.emplace(p);
                    q.emplace_back(r, c + 1, t + 1);
                }
            }

        REP(k, h) REP(l, w) {
            if (s[k][l] == '#') continue;
            // cout << "---------" << EOL; cout << i << ":" << j << "//" << k << ":" << l << EOL;
            chmax(ans, d[k][l]);
        }
    }
    cout << ans << EOL;
}


Measured memory_bytes: 256
N, K = (int(x) for x in input().split())
if K > (N-1) * (N-2) // 2:
    ans = False
else:
    ans = True
if(not ans):
    print('-1')
else:
    E = (N-1) * (N-2) // 2 - K
    ans1 = E + N - 1
    print('%d' % ans1)
    for i in range(N-1):
        print('1 %d' % (i+2))
    p = 2
    q = 3
    for i in range(E):
        print('%d %d' % (p, q))
        q += 1
        if q > N:
            p += 1
            q = p + 1

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

int main() {
  int N, A, B;
  string S;
  int d = 0;
  int f = 0;
  int ff = 0;

  cin >> N >> A >> B >> S;

  for (int i = 0; i < S.size(); i++)
  {
    char c = S[i];
    if (c == 'a') d++;
    if (c == 'b') {
      f++;
      if (f <= B) {
        ff = f;
      }
      else {
        ff = B;
      }
    }
    if (d + ff <= A + B && (c == 'a' || c == 'b' && f <= B)) {
      cout << "Yes" << endl;
    }
    else {
      cout << "No" << endl;
    }
  }
}

Measured memory_bytes: 3752
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <numeric>
using namespace std;
typedef long long ll;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int s,w;cin>>s>>w;
    if(w>=s)cout<<"unsafe";
    else cout<<"safe";
    
}

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


int main()
{
	int N;
	int a[100005];
	cin >> N;

	for (int i = 0; i < N;i++ ) {
	
		cin >> a[i];
	}
	int count = 0;
	sort(a, a + N);

	int i = 0;
	while( i < N ) {
		int j = i + 1;
		count++;
		while (a[i] == a[j]) {
			j++;
		}
		if ((j - i) % 2 == 0)count--;
		i = j;
	}

	cout << count;
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <limits>
#include <stack>
#include <queue>
#include <map> 
using namespace std;

#define LL long long


int main() {
	LL N, K;

	cin >> N >> K;

	static double dp[200100];
	memset(dp, 0, sizeof(dp));

	for (int i = 1; i <= N; i++) {
		dp[i] = 1.0 / (double)N;
	}

	for (LL i = 1; i < K; i++) {
		dp[i * 2] += dp[i] * 0.5;
	}

	double result = 0;

	for (LL i = K; i < 200100; i++) {
		result += dp[i];
	}

	printf("%0.11f\n", result);

	return 0;
}

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

using namespace std;
using ll=long long;

int main()
{
   ll k,a,b;
   cin >>k >>a >>b;
   ll ans=1;
   if(k<=a-1){
    cout << ans+k<< endl;
    return 0;
   }
   else {
    if(b-a<=2){
         cout << ans+k<< endl;
        return 0;
    }
    ans=a;k-=(a-1);
        ans+=(b-a)*(k/2)+k%2;
        cout << ans << endl;
   }
    return 0;
}


Measured memory_bytes: 256
import std.stdio;
import std.algorithm;
import std.range;
import std.conv;
import std.string;

int f(int a, int k) {
    if (a < k) return 0;
    if (a%k == 0) return a/k;
    int c = a/k+1;
    int l = a/k*k;
    a -= ((a-l-1)/c+1)*c;
    return f(a, k);
}

void main() {
    int n = to!int(chomp(readln()));
    //int m = 100;
    //int[] dp = new int[m+1];
    //foreach (i; 0..m+1) {
    //    int[] s = new int[m+1];
    //    foreach (j; 1..i/n+1) {
    //        s[dp[i-j]] = 1;
    //    }
    //    foreach (j; 0..m) {
    //        if (s[j] == 1) continue;
    //        dp[i] = j;
    //        break;
    //    }
    //    writefln("%2d : %2d - %2d", i, dp[i], f(i,n));
    //}
    //return;
    int x = 0;
    foreach (i; 0..n) {
        string[] input = split(readln());
        int a = to!int(input[0]);
        int k = to!int(input[1]);
        x ^= f(a,k);
    }
    writeln(x ? "Takahashi" : "Aoki");
}

Measured memory_bytes: 380
s=input()
k=int(input())

def count_change(st):
    st=st+'!'
    cnt=0
    moji=st[0]
    l=0
    r=0
    for i in range(1,len(st)):
        if moji!=st[i]:
            cnt+=(r-l+1)//2
            l=i
            r=i
            moji=st[i]
        else:
            r=i

    return cnt

if len(set(s))==1:
    ans=len(s)*k//2
    print(ans)
    exit()

if s[0]==s[-1]:
    a=1
    for i in range(len(s)):
        if s[i]!=s[i+1]:
            break
        else:
            a+=1
    
    b=1
    for i in range(len(s)-1,0,-1):
        if s[i]!=s[i-1]:
            break
        else:
            b+=1
    
    ans=count_change(s)*k-(a//2+b//2-(a+b)//2)*(k-1)

else:
    ans=count_change(s)*k

print(ans)

Measured memory_bytes: 9260
#include<iostream>

using namespace std;

int main()
{
	int N;
	long long power = 1;

	cin >> N;

	for(int i=1;i<=N;i++)
	{
		power *= i;
		power %= (long long)(1000000007);
	}

	cout << power << endl;

	return 0;
}

Measured memory_bytes: 256
//in the name of god
#include <bits/stdc++.h>
using namespace std;
#define MAX_N (int)1e5+20
#define INF 1e9+20
#define pb push_back
#define F first
#define S second
typedef long long LL;
typedef pair<int,int> pii;
const int delta=(int)1e9+7;
int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
    string s; cin>>s;
    for(int i=0;i<s.size()-8;++i) cout<<s[i];
	return cout<<endl,0;
}

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

int main()
{
  int X, Y;
  int res=0;
  cin >> X >> Y;

  cout << X+Y/2 << endl;
}


Measured memory_bytes: 256
import collections

N = int(input())
A = list(map(int, input().split()))

cnt = collections.Counter(A)
k2 = []
k4 = []
for k in cnt:
    if cnt[k] >= 2:
        k2.append(k)
    if cnt[k] >= 4:
        k4.append(k)
ans = 0
k2.sort()
k4.sort()
if len(k4) >= 1:
    ans = max(ans, k4[-1] * k4[-1])
if len(k2) >= 2:
    ans = max(ans, k2[-1] * k2[-2])
print(ans)


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

struct RU {
	using t1 = int;
	using t2 = int;
	static t2 id2() { return -1; }
	static t1 op2(const t1& l, const t2& r) { return r == id2() ? l : r; }
	static t2 op3(const t2& l, const t2& r) { return r == id2() ? l : r; }
};

template <typename M>
class lazy_segment_tree {
	using T1 = typename M::t1;
	using T2 = typename M::t2;
	const int h, n;
	const vector<T1> data;
	vector<T2> lazy;
	void push(int node) {
		if (lazy[node] == M::id2()) return;
		lazy[node << 1] = M::op3(lazy[node << 1], lazy[node]);
		lazy[(node << 1) | 1] = M::op3(lazy[(node << 1) | 1], lazy[node]);
		lazy[node] = M::id2();
	}
public:
	lazy_segment_tree(int n_, T1 v1)
		: h(ceil(log2(n_))), n(1 << h), data(n_, v1), lazy(n << 1, M::id2()) {}
	lazy_segment_tree(const vector<T1>& data_)
		: h(ceil(log2(data_.size()))), n(1 << h), data(data_), lazy(n << 1, M::id2()) {}
	void update(int l, int r, T2 val) {
		l += n, r += n;
		for (int i = h; i > 0; i--) push(l >> i), push(r >> i);
		r++;
		while (l < r) {
			if (l & 1) lazy[l] = M::op3(lazy[l], val), l++;
			if (r & 1) r--, lazy[r] = M::op3(lazy[r], val);
			l >>= 1; r >>= 1;
		}
	}
	T1 find(int p) const {
		T1 res = data[p]; p += n;
		while (p) res = M::op2(res, lazy[p]), p >>= 1;
		return res;
	}
};

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int n, q;
	cin >> n >> q;
	lazy_segment_tree<RU> lst(n, INT_MAX);
	while (q--) {
		int com;
		cin >> com;
		if (com == 0) {
			int s, t, x;
			cin >> s >> t >> x;
			lst.update(s, t, x);
		}
		else {
			int p;
			cin >> p;
			printf("%d\n", lst.find(p));
		}
	}
	return 0;
}



Measured memory_bytes: 4616
#include<stdio.h>

 int main(void)

{

   int W,H,x,y,r;

   scanf("%d %d %d %d %d",&W,&H,&x,&y,&r);

   if(W<x+r||x-r<0||H<y+r||y-r<0){

      printf("No\n");

   }else{

      printf("Yes\n");

   }

   return 0;

}

Measured memory_bytes: 584
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;
const long long INF = 1LL << 60;
typedef pair<int, int> P;
int main()
{
    int N;
    cin >> N;

    vector<vector<P>> xy(N);
    int ans = 0;
    rep(i, N) {
        int A;
        cin >> A;
        rep(j, A) {
            int x, y;
            cin >> x >> y;
            xy[i].push_back(P(x, y));
        }
    }

    for (int bit = 1; bit < (1 << N); bit++) {
        vector<int> check(N, 0), han(N, -1);
        bool flag = true;
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            if (bit & (1 << i)) {
                check[i] = 1;
                for (int j = 0; j < (int)xy[i].size(); j++) {
                    P p = xy[i][j];
                    if (p.second == 1) check[p.first - 1] = 1;
                }
            }
        }
        /*
        for (int i = 0; i < N; i++) {
            if (check[i] == 1) {
                for (int j = 0; j < (int)xy[i].size(); j++) {
                    P p = xy[i][j];
                    if (p.second == 1) check[p.first - 1] = 1;
                }
            }
        }*/
        for (int i = 0; i < N; i++) {
            if (check[i] == 1) {
                for (int j = 0; j < (int)xy[i].size(); j++) {
                    P p = xy[i][j];
                    if (check[p.first - 1] != p.second) {
                        flag = false;
                        break;
                    }
                }
            }
        }
        if (flag) {
            rep(i, N) cnt += max(check[i], 0);
        }
        if (flag) ans = max(ans, cnt);
    }

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

Measured memory_bytes: 256
#include<stdio.h>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<string>
#include<stack>
#include<math.h>
#include<set>
using namespace std;

int n,k,w[100005];
typedef long long int ll;
int check(ll p){
	int j=0;
	for(int i=0;i<k;i++){
		ll s=0;
		while(s+w[j]<=p){
			s+=w[j];
			j++;
			if(j==n)
				return 1;
		}
	}
	return 0;
}
ll ef(){
	ll i=0,j=100000*10000,m;
	while(i<j){
		m=(i+j)/2;
		if(check(m))j=m;
		else i=m+1;
	}
	return j;
}
int main(){
	cin>>n>>k;
	for(int i=0;i<n;i++)
		scanf("%d",&w[i]);
	int ans=ef();
	cout<<ans<<endl;
}


Measured memory_bytes: 3544
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

const int mod = 1e9 + 7;
int h, w;
llong k;

char grid[1000][1001];
int hc, vc;

int ipow(int x, llong p) {
    if (p == 0) return 1;
    if (p == 1) return x;
    int ret = ipow(x, p >> 1);
    ret = (llong)ret * ret % mod;
    if (p & 1) ret = (llong)ret * x % mod;
    return ret;
}

int main() {
    scanf("%d%d%lld", &h, &w, &k);
    if (k-- == 0) {
        printf("1\n");
        return 0;
    }
    int cnt = 0;
    for (int i = 0; i < h; ++i) {
        scanf("%s", grid[i]);
        for (int j = 0; j < w; ++j) {
            if (grid[i][j] == '#') ++cnt;
        }
    }
    
    for (int i = 0; i < h; ++i) {
        if (grid[i][0] == '#' && grid[i][w - 1] == '#') ++vc;
    }
    
    for (int i = 0; i < w; ++i) {
        if (grid[0][i] == '#' && grid[h - 1][i] == '#') ++hc;
    }
    if (hc && vc) {
        printf("1\n");
        return 0;
    }
    if (hc == vc) {
        printf("%d\n", ipow(cnt, k));
        return 0;
    }
    if (vc) {
        for (int i = 0; i < h || i < w; ++i) {
            for (int j = 0; j < h || j < w ; ++j) {
                if (i < j) swap(grid[i][j], grid[j][i]);
            }
        }
        swap(h, w);
        swap(hc, vc);
    }
    
    int cp = 0;
    for (int i = 1; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (grid[i - 1][j] == '#' && grid[i][j] == '#') ++cp;
        }
    }
    
    int ans = cp, a, b;
    if (cnt != hc) {
        a = ipow(cnt - hc, mod - 2);
        b = (ipow(cnt, k) + mod - ipow(hc, k)) % mod;
    }
    else {
        a = 1;
        b = k % mod * ipow(hc, k - 1) % mod;
    }
    ans = (llong)ans * a % mod * b % mod;
    ans = ipow(cnt, k) + mod - ans;
    printf("%d\n", ans % mod);
    
	return 0;
}


Measured memory_bytes: 1408
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>
#include <numeric>

using namespace std;

#define mod 1000000007

int main(){
  int n;
  cin >> n;
  long long int ans = 0;
  for(int i = 0; i < n; i++){
    int l, r;
    cin >> l >> r;
    ans += r - l + 1;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>

using namespace std;

int modpow(int x, int p)
{
	int t = p - 2;
	int m = x;
	int r = 1;
	
	while (t){
		if (t & 1){
			r = r * m % p;
		}
		m = m * m % p;
		t >>= 1;
	}
	return (r);
}

int p;

typedef struct {
    int value;
    int pos;
} result;

result ng = {-1, -1};

result equation(char *s, int pos);
result factor(char *s, int pos);
result term(char *s, int pos);

result equation(char *s, int pos)
{
    result temp, next;
    temp = factor(s, pos);
    while (s[temp.pos] == '+' || s[temp.pos] == '-'){
        next = factor(s, temp.pos + 1);
		if (next.pos == -1) return (ng);
        if (s[temp.pos] == '+'){
            temp.value += next.value;
			temp.value %= p;
        }
        else {
            temp.value += (p - next.value);
			temp.value %= p;
        }
        temp.pos = next.pos;
    }
    
    return (temp);
}

result factor(char *s, int pos)
{
    result temp, next;
    temp = term(s, pos);
    while (s[temp.pos] == '*' || s[temp.pos] == '/'){
        next = term(s, temp.pos + 1);
		if (next.pos == -1) return (ng);
		if (s[temp.pos] == '/'){
			if (!next.value) return (ng);
			next.value = modpow(next.value, p);
		}
        temp.value *= next.value;
		temp.value %= p;
        temp.pos = next.pos;
    }
    
    return (temp);
}

result term(char *s, int pos)
{
    int i;
    int value;
    result temp;
    
    if (s[pos] == '('){
        temp = equation(s, pos + 1);
		if (temp.pos == -1) return (ng);
        temp.pos += 1;
        return (temp);
    }
    else {
        value = 0;
        while ('0' <= s[pos] && s[pos] <= '9'){
            value = value * 10 + (s[pos++] - '0');
        }
        temp.value = value % p;
        temp.pos = pos;
        return (temp);
    }
}


int main()
{
	result res;
	char exp[100000], str[100000];
	while (scanf("%d:", &p) && p){
		fgets(exp, 100000, stdin);
		int k = 0;
		for (int i = 0; exp[i] != '\0'; i++){
			if (exp[i] == ' ' || exp[i] == '\n'){
				continue;
			}
			str[k++] = exp[i];
		}
		str[k] = '\0';
		res.pos = 0;
		res = equation(str, 0);
		if (res.pos != -1){
			printf("%s = %d (mod %d)\n", str, res.value, p);
		}
		else {
			printf("NG\n");
		}
	}
	
	return (0);
}

Measured memory_bytes: 1196
s=input()
if s == 'SAT':
    print(1)
if s == 'SUN':
    print(7)
if s == 'MON':
    print(6)
if s == 'TUE':
    print(5)
if s == 'WED':
    print(4)
if s == 'THU':
    print(3)
if s == 'FRI':
    print(2)

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

using namespace std;

/**
 *  Name: Chris M. Perez
 *  University: Interamerican University Metro Campus
 *
**/

#define endl '\n'
#define MOD 10E9
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define gcd(x , y) __gcd(x , y)
#define all(x) (x).begin() , (x).end()
#define forn(i , a , b) for(int i=(a);i<(b);i++)
#define forrange(j , a , b) for(int j=(a);j<=(b);j++)
#define nestedforn(i , a , b , j , c , d) for(int i=(a);i<=(b);i++) for(int j=(c);j<=(d);j++)
#define sort_all(x) sort(all(x))
#define zeros_at_beginning(x) __builtin_clz(x)
#define zeros_at_end(x) __builtin_ctz(x)
#define ones(x) __builtin_popcount(x)
#define parity_even_or_odd_ones __builtin_parity(x)


typedef vector<int> vi;
typedef pair<int , int> pii;
typedef tuple<int , int , int> tiii;
typedef vector<pii> vpii;
typedef vector<tiii> vtiii;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef long long ll;
typedef long long int lli;

                                                                    
int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.precision(10);
  cout << fixed;  

#ifdef LOCAL_DEFINE
  freopen("input.txt" , "rt" , stdin);
#endif
    
  int a; cin >> a;
  int p; cin >> p;
  cout << (int)(((a * 3) + p) / 2) << endl;
   
          
#ifdef LOCAL_DEFINE 
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif  
  return 0;
}

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

// Inserted snippets: io, root
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
template<typename H> bool chmin(H& v1, const H v2) { if (v1 > v2) { v1 = v2; return true; } return false; }
template<typename H> bool chmax(H& v1, const H v2) { if (v1 < v2) { v1 = v2; return true; } return false; }
template<typename H> void read(H& head) { cin >> head; }
template<typename H, typename ...T> void read(H& head, T& ...tail) { cin >> head; read(tail...); }
template<typename H> void write(H head) { cout << head << '\n'; }
template<typename H, typename ...T> void write(H head, T ...tail) { cout << head << " "; write(tail...); }
template<typename ...T> void die(T ...tok) { write(tok...); exit(0); }
// End snippets

int D, c[27];
int s[366][27];

chrono::steady_clock::time_point program_begin;

double runtime() {
	chrono::steady_clock::time_point program_end = chrono::steady_clock::now();

	return chrono::duration_cast<chrono::microseconds>(program_end - program_begin).count() / 1000000.0;
}

int calc(vector<int> sc) {
	vector<int> last(27, 0);
	int val = 0;
	rep(d, 1, D + 1) {
		val += s[d][sc[d]];
		last[sc[d]] = d;
		rep(i, 1, 27)
			val -= c[i] * (d - last[i]);
	}
	return val;
}

int myrand(int a, int b) {
	return a + rand() % (b - a + 1);
}

void solve() {
	vector<int> ans(366), best_ans(366);
	int best_ans_val = -50000000;
	int cur_val = calc(ans);

	for (int i = 1; i <= 365; i++)
		ans[i] = i % 26 + 1;

	{
		int val = calc(ans);
		if (val > best_ans_val) {
			best_ans_val = val;
			best_ans = ans;
		}
	}

	double T1 = 0.4;
	double T2 = 1.8;

	auto rng = default_random_engine {};
	while (runtime() <= T1 / 2) {
		for (int i = 1; i + 25 <= 365; i += 26) {
			shuffle(ans.begin() + i, ans.begin() + i + 26, rng);
		}

		int val = calc(ans);
		if (val > best_ans_val) {
			best_ans_val = val;
			best_ans = ans;
		}
	}
	while (runtime() <= T1) {
		for (int i = 1; i <= 365; i++)
			ans[i] = myrand(1, 26);

		int val = calc(ans);
		if (val > best_ans_val) {
			best_ans_val = val;
			best_ans = ans;
		}
	}
	
	ans = best_ans;
	cur_val = best_ans_val;

	//cerr << "INIT:" << best_ans_val << endl;

	while (runtime() <= T2) {
		vector<int> new_ans = ans;
		int d = myrand(1, 365), n = myrand(1, 26);
		new_ans[d] = n;
		int new_val = calc(new_ans);
		
		double base_proc = exp(-50.0 * (runtime() - T1) / (T2 - T1));
		double rand_double = 1.0 * rand() / RAND_MAX;
		bool accept =
			rand_double < base_proc * (1.0 * new_val / best_ans_val);
		
		if (new_val > cur_val || accept) {
			ans = new_ans;
			cur_val = new_val;

			if (chmax(best_ans_val, cur_val)) {
				best_ans_val = cur_val;
				best_ans = ans;
			}
		}
	}

	rep(i, 1, D + 1)
		write(best_ans[i]);
}

void test() {}

int main(int argc, char *argv[]) {
	//cin.tie(0)->sync_with_stdio(0);
	//cin.exceptions(cin.failbit);

	srand(time(NULL));

	program_begin = chrono::steady_clock::now();

	read(D);
	rep(i, 1, 27) read(c[i]);
	rep(i, 1, D + 1) rep(j, 1, 27) read(s[i][j]);
	
	solve();
}


Measured memory_bytes: 4304
inputa = input().split()
inputb = list(input())
if inputb[int(inputa[1])-1] == "A":
  inputb[int(inputa[1])-1] = "a"
if inputb[int(inputa[1])-1] == "B":
  inputb[int(inputa[1])-1] = "b"
if inputb[int(inputa[1])-1] == "C":
  inputb[int(inputa[1])-1] = "c"

print("".join(inputb))

Measured memory_bytes: 3064
# coding=utf-8

import sys
stdin = sys.stdin
def na(): return map(int, stdin.readline().split())
def ns(): return stdin.readline().strip()

def main():
    sx,sy,tx,ty = na()
    # sx,sy,tx,ty=0,0,1,2
    ret = ""
    for i in range(tx-sx):
        ret += "R"
    for i in range(ty-sy):
        ret += "U"
    for i in range(tx-sx):
        ret += "L"
    for i in range(ty-sy):
        ret += "D"
    ret += "D"
    for i in range(tx-sx+1):
        ret += "R"
    for i in range(ty-sy+1):
        ret +="U"
    ret += "L"
    ret += "U"
    for i in range(tx-sx+1): ret += "L"
    for i in range(ty-sy+1): ret += "D"
    ret += "R"
    print(ret)
    pass


if __name__ == '__main__':
    main()

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

class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		int[][] cost = new int[n][n];

		for (int i=0; i<n; i++) {
			Arrays.fill(cost[i],-1);
		}

		for (int i=0; i<n; i++) {
			String line = br.readLine();
			String[] str = line.split(" ");
			int id = Integer.parseInt(str[0]);
			for (int j=2; j<str.length-1; j+=2) {
				cost[id][Integer.parseInt(str[j])] = Integer.parseInt(str[j+1]);
			}
		}

		boolean[] flag = new boolean[n];
		int[] d = new int[n];
		boolean fin = false;

		Arrays.fill(d,-1);
		flag[0] = true;
		d[0] = 0;
		int now = 0;

		while (!fin) {
			for (int i=0; i<n; i++) {
				if (cost[now][i] != -1 && !flag[i]) {
					if (d[i] == -1)
						d[i] = d[now]+cost[now][i];
					else
						d[i] = Math.min(d[i],d[now]+cost[now][i]);
				}
			}

			fin = true;
			int min = Integer.MAX_VALUE;

			for (int i=0; i<n; i++) {
				if (min > d[i] && d[i] != -1 && !flag[i]) {
					min = d[i];
					now = i;
					fin = false;
				}
			}
			flag[now] = true;
		}

		for (int i=0; i<n; i++) {
			System.out.println(i+" "+d[i]);
		}

		br.close();
	}
}

Measured memory_bytes: 22644
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define per(i,b,a) for(int i=b;i>=a;i--)
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Forenska(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sqr(x) ((x)*(x))
#define lowbit(x) ((x)&(-x))
#define GREATER(x) x,vector<x>,greater<x>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pLL;
typedef vector<int> vec;
typedef vector<LL> vecL;
typedef vector<pii> vecP;
typedef vector<pLL> vecPL;
typedef vector<string> vecS;
typedef vector<vec> mat;
typedef complex<double> point;
const long double PI=3.1415926535897932384626433832795028841971693993751058209749445923078164062862089;
const LL INFLL=0x3f3f3f3f3f3f3f3f;
const int INF=0x3f3f3f3f;
const long double EPS=1e-10;
int read()
{
	int x=0;
	char ch=' ';
	bool flag=false;
	while(!isdigit(ch))
	{
		if(ch=='-')flag=true;
		ch=getchar();
	}
	while(isdigit(ch))
	{
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return flag?-x:x;
}
const int MAX_N=2050;
const int MAX_V=40050;
int n,m;
int a[MAX_N];
bool b[MAX_N][MAX_N];
int ans[MAX_N];
int ansSz;
bool inAns[MAX_N];
int lastNotCoPrime[MAX_N];
int minOnSuff[MAX_N];
int comp[MAX_V];
vec g[MAX_V];
int C;
int bestForCol[MAX_N];
map <int,int> primeId;
int getId(int p)
{
	if(primeId.count(p)>0)return primeId[p];
	primeId[p]=m;
	m++;
	return m-1;
}
void dfs(int v)
{
	comp[v]=C;
	rep(i,0,g[v].size())
	{
		int u=g[v][i];
		if(comp[u]!=-1)continue;
		if(u<n && inAns[u])continue;
		dfs(u);
	}
}
void color()
{
	rep(i,0,m)
	{
		comp[i]=-1;
	}
	C=0;
	rep(i,0,n)
	{
		if(inAns[i])continue;
		if(comp[i]!=-1)continue;
		dfs(i);
		C++;
	}
}
int main()
{
	cin>>n;
	m=n;
	rep(i,0,n)
	{
		cin>>a[i];
		int x=a[i];
		For(y,2,sqrt(x))
		{
			if(x%y!=0)continue;
			int id=getId(y);
			g[i].pb(id);
			g[id].pb(i);
			while(x%y==0)x/=y;
		}
		if(x!=1)
		{
			int id=getId(x);
			g[i].pb(id);
			g[id].pb(i);
		}
	}
	rep(i,0,n)
	{
		rep(j,i+1,n)
		{
			if(__gcd(a[i],a[j])>1)
			{
				b[i][j]=b[j][i]=1;
			}
		}
	}
	rep(i,0,n)lastNotCoPrime[i]=-1;
	rep(i,0,n)minOnSuff[i]=INF;
	while(ansSz!=n)
	{
		color();
		rep(i,0,C)bestForCol[i]=-1;
		rep(i,0,n)
		{
			if(inAns[i])continue;
			if(minOnSuff[lastNotCoPrime[i]+1]<a[i])continue;
			if(bestForCol[comp[i]]==-1 || a[bestForCol[comp[i]]]>a[i])
			{
				bestForCol[comp[i]]=i;
			}
		}
		int id=-1;
		rep(i,0,C)
		{
			if(bestForCol[i]==-1)continue;
			if(id==-1 || a[id]<a[bestForCol[i]])id=bestForCol[i]; 
		}
		if(id==-1)throw;
		inAns[id]=1;
		ans[ansSz++]=a[id];
		rep(i,0,ansSz)minOnSuff[i]=min(minOnSuff[i],a[id]);
		rep(i,0,n)if(b[id][i])lastNotCoPrime[i]=ansSz-1;
	}
	rep(i,0,n)cout<<ans[i]<<" ";
	cout<<endl;
	return 0;
}



Measured memory_bytes: 5632
#define _USE_MATH_DEFINES
#include  <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include<math.h>
#include<iomanip>
#include<stdio.h>
#include <stdlib.h>
#include<stdio.h>
#include <queue>
#include<map>
#include <sstream>
#include<set>
#include<stack>

//#include<bits/stdc++.h>


using namespace std;



int main() {
	
	
	int n;
	cin >> n;
	map<string, bool>f;
	bool g = 0;
	char c;
	for (int i = 0; i < n; i++) {
		string a;
		cin >> a;
		if (f[a])g = 1;
		f[a] = 1;
		if (i) {
			if (c != a[0])g = 1;
		}
		c = a[a.size() - 1];
	}
	if (g)cout << "No" << endl;
	else cout << "Yes" << endl;
	return 0;

}

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

using ll = long long;

long long MOD = 1e9+7;

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

// a^{-1} mod を計算する
long long modinv(long long a, long long mod) {
    return modpow(a, mod - 2, mod);
}

long long nCr(long long n, long long r){
    long long x = 1, y = 1;
    for(int i = 0; i < r; i++){
        x = x*(n - i) % MOD;
        y = y*(i+1) % MOD;
    }
    return x*modinv(y,MOD) % MOD;
}

long long modfact(long long x){
    long long res = 1;
    for(long long i = 1; i <= x; i++){
        res *= i;
        res %= MOD;
    }
    return res;
}

int main(){
    ll n, k; 
    cin >> n >> k;
    ll r = n - k; //赤玉の個数
    vector<ll> ans;
    for(int i = 0; i < k; i++){
        if(i <= min(k-1,r+1)){
            ll res = nCr(k-1,i) % MOD;
            res = res*nCr(r+1, i+1) % MOD;
            ans.push_back(res);
        }else{
            ans.push_back(0);
        }
    }
    rep(i,k) cout << ans[i] << endl;
}

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

char buf[114514];
string s1;
string s2;

int main() {
  scanf("%s", buf);
  s1 = buf;

  map<char, char> rev;
  rev['b'] = 'd';
  rev['d'] = 'b';
  rev['p'] = 'q';
  rev['q'] = 'p';
  for (int i=s1.size()-1; i>=0; i--) {
    s2 += rev[s1[i]];
  }

  if (s1 == s2) puts("Yes");
  else puts("No");
}


Measured memory_bytes: 640
#include <cstdio>
#include <cctype>
#include <vector>
using namespace std;

#define si static inline
#define gcu getchar_unlocked
si int in() {
	int c, n = 0;
	bool minus = false;
	if ((c = gcu()) == '-') minus = true;
	else ungetc(c, stdin);
	while ((c = gcu()) >= '0' && c <= '9') n = 10 * n + (c - '0');
	return minus ? -n : n; }
si void scan(char *s) {while (!isspace(*s++ = gcu()));}
#define pcu putchar_unlocked
#define svo si void out
svo(int n) {
	static char buf[20];
	char *p = buf;
	if(n < 0) pcu('-'), n *= -1;
	if (!n) *p++ = '0';
	else while (n) *p++ = n % 10 + '0', n /= 10;
	while (p != buf) pcu(*--p); }
svo(const char *s){while(*s)pcu(*s++);}
//svo(char *s){while(*s)pcu(*s++);}
svo(char c){pcu(c);}
template <typename T>
svo(vector<T> v){for(T &x:v)out(' '),out(x);out('\n');}
//svo(vector<T> &v){for(int &x:v)out(&x == &v[0]?"":" ",x);out('\n');}
template <typename head, typename... tail>
svo(head&& h, tail&&... t){out(h);out(move(t)...);}

typedef vector<int> v;

struct bst
{
	struct node { int v, l = -1, r = -1; };
	int root = -1, i = 0;
	vector<node> nodes;

	bst(int n)
	{
		nodes.resize(n);
	}

	int insert (int r, int v)
	{
		if (r == -1) {
			nodes[i].v = v;
			return i++;
		}
		node &n = nodes[r];
		if (n.v < v)
			n.r = insert(n.r, v);
		else
			n.l = insert(n.l, v);
		return r;
	}
	void insert (int n)
	{
		root = insert(root, n);
	}
	bool find(int r, int v)
	{
		if (r == -1)
			return false;
		node &n = nodes[r];
		return n.v == v ? true : n.v < v ? find(n.r, v) : find(n.l, v);
	}
	bool find (int n)
	{
		return find(root, n);
	}
	void print(int r, v &buf)
	{
		if (r == -1)
			return;
		node n = nodes[r];
		buf.push_back(n.v);
		print(n.l, buf);
		out(' ', n.v);
		print(n.r, buf);
	}
	void print()
	{
		v buf;
		print(root, buf);
		out('\n', buf);
	}
};

int main()
{
	int n = in();
	char s[20];
	bst b(n);

	while (n--) {
		scan(s);
		switch(*s) {
		case 'i':
			b.insert(in()); break;
		case 'f':
			out(b.find(in()) ? "yes\n": "no\n"); break;
		default:
			b.print();
		}
	}
}



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

#define ll long long
#define mii make_pair<int, int>
#define mll make_pair<ll, ll>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define rep(i, a, b) for (int i = a; i < b; ++i)
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vvb vector<vector<bool>>

bool cmp(pair<int, ll> p1, pair<int, ll> p2)
{
    return p1.second < p2.second;
}

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

    int n;
    string s;
    cin >> n >> s;

    ll r = 0, g = 0, b = 0;
    for (int i = 0; i < n; ++i)
    {
        if (s[i] == 'R')
            r++;
        if (s[i] == 'G')
            g++;
        if (s[i] == 'B')
            b++;
    }
    ll m = 0;
    for (int i = 1; i < n - 1; ++i)
    {
        for (int j = 1; j <= i && j <= n - i - 1; ++j)
            if (s[i - j] != s[i + j] && s[i - j] != s[i] && s[i + j] != s[i])
                m++;
    }
    cout << r * g * b - m;
}

Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define dup(x,y) (((x)+(y)-1)/(y))
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> pii;
const double EPS = 1e-10;
const int INF = 1e9;
const ll LINF = 1e15;
const int MOD = 1000000007;
const double PI = acos(-1);
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

int main() {
	int h, w;
	cin >> h >> w;
	vector<string> g(h);
	rep(i,h) cin >> g[i];
	int ans = 0;

	rep(si, h) {
		rep(sj, w) {
			queue<pii> q;
			vector<vector<int>> dist(h, vector<int>(w, INF));
			auto push = [&](int i, int j, int d) {
				if (i < 0 || j < 0 || i >= h || j >= w) return;
				if (g[i][j] == '#') return;
				if (dist[i][j] != INF) return;
				dist[i][j] = d + 1;
				q.push(pii(i,j));
			};
			push(si, sj, -1);
			while (!q.empty()) {
				auto p = q.front(); q.pop();
				rep(d, 4) {
					int ni = p.first + dy[d];
					int nj = p.second + dx[d];
					push(ni, nj, dist[p.first][p.second]);
				}
			}
			rep(i,h) rep(j,w) {
				if (dist[i][j] == INF) continue;
				ans = max(ans, dist[i][j]);
			}

		}
	}
	cout << ans << endl;
}

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

#define ll long long
#define fo(i,n) for(ll i=0; i<(n); i++)
#define FO(i,a,b) for(auto i=a; i!=(b); i+=(b)>(a)?1:-1)
#define vll vector<ll>
#define vch vector<char>
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sll set<ll>
#define all(c) c.begin(), c.end()
#define on(x) cout<<x<<"\n";
#define os(x) cout<<x<<' ';
#define nl cout<<"\n";

ll gcd(ll a, ll b)
{
    if(a==b)
        return a;
    if(a>b)
        return gcd(a-b, b);
    return gcd(a, b-a);
}

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

    ll n, ans=0;
    cin>>n;
    FO(i, 1, n+1)
    {
        FO(j, 1, i+1)
        {
            FO(k, 1, j+1)
            {
                ll x;
                if(i==j && j==k) x=i;
                else if(i==j) x=3*gcd(i, k);
                else if(j==k) x=3*gcd(i, j);
                else x=6*gcd(i, gcd(j, k));
                ans+=x;
            }
        }
    }
    on(ans)
    return 0;
}

Measured memory_bytes: 3628
#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
import math
import itertools
from collections import defaultdict
from collections import Counter
import numpy as np

import heapq

def bfs(c,nu,di,node,val):
    c[nu]=True
    di[val[nu]]+=1
    for each in node[nu]:
        if c[each]:
            continue
        di=bfs(c,each,di,node,val)
    return di





n,k=list(map(int,input().split()))
h=list(map(int,input().split()))
#node=[i for i in h]
node=[defaultdict(int) for _ in range(n) ]
for _ in range(k):
    i,v=list(map(int,input().split()))
    i-=1
    v-=1
    """
    if node[i]>node[v]:
        node[v]=node[i]
    elif node[i]<node[v]:
        node[i]=node[v]
    """
    #node[i]=max(node[i],h[v])
    #node[v]=max(node[v],h[i])
    #node[i].append(v)
    #node[v].append(i)
    node[i][h[v]]+=1
    node[v][h[i]]+=1

#print(node)
check=[False for _ in range(n)]
ans=0
for i in range(n):
    t=node[i]
    if len(t)==0:
        ans+=1
        continue
    if max(t.keys())<h[i]:
        #print(i)
        ans+=1
print(ans)
    


Measured memory_bytes: 61808
def resolve():
    import math
    N = int(input())
    price = N/1.08
    reTaxprice1 = math.floor(math.floor(price)*1.08)
    reTaxprice2 = math.floor(math.ceil(price)*1.08)
    if reTaxprice1 == N:
        print(math.floor(price))
    elif reTaxprice2 == N:
        print(math.ceil(price))
    else:
        print(':(')
resolve()

Measured memory_bytes: 38384
#include <stdio.h>
#include <string.h>
#include<math.h>
int main()
{
    long long n,k,a,b,i,ans=0;
    scanf("%lld%lld",&n,&k);
    if(k==0) printf("%lld\n",n*n);
    else{
    for(b=k+1;b<=n;b++)
    {
        ans+=(n/b)*(b-k);
        if(n%b>=k)
            ans+=n%b-k+1;
    }
    printf("%lld\n",ans);}
}


Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <cassert>
#include <queue>
#include <map>
#include <set>
using namespace std;
using Int = int64_t;
using P = pair<Int, Int>;
const Int INF = 1<<30;
const Int MOD = (Int)1e9 + 7;
const Int MAX_N = (Int)1e5 + 5;
#define debug(x) cout << #x << ": " << x << endl
#define debug2(x, y) cout << #x << ": " << x << ", " << #y << ": " << y << endl;
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2>& p) { os << p.first << " " << p.second; return os; }
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) { for(Int i = 0; i < (Int) v.size(); i++) os << v[i] << (i + 1 != v.size() ? " " : ""); return os; }

Int GCD(Int a, Int b)
{
    if (a < 0)
        a = -a;
    if (b < 0)
        b = -b;
    if (b == 0)
        return a;
    else
        return GCD(b, a % b);
}

vector<Int> eratosthenes(const Int &N)
{
    vector<Int> is_prime(N + 1);
    for(int i = 0; i < is_prime.size(); i++) is_prime[i] = i;
    is_prime[1] = 0;

    for(Int i = 2; i * i <= N; i++)
    {
        if(is_prime[i] != i) continue;
        for(Int j = 2 * i; j <= N; j += i)
        {
            is_prime[j] = min(is_prime[j], i);
        }
    }
    return is_prime;
}

map<Int, Int> prime_factor(Int N, const vector<Int> &is_prime)
{
    map<Int, Int> result;
    while(N > 1)
    {
        // N = x * p(=is_prime[N]) 
        result[is_prime[N]]++;
        N = N / is_prime[N];
    }
    return result;
}



void solve()
{
    Int N; cin >> N;
    vector<Int> A(N);
    for(Int i = 0; i < N; i++)
    {
        cin >> A[i];
    }

    vector<Int> is_prime = eratosthenes(*max_element(A.begin(), A.end()) + 1);

    vector<map<Int, Int>> buff;
    map<Int, Int> mp;
    for(Int i = 0; i < N; i++)
    {
        map<Int, Int> tmp = prime_factor(A[i], is_prime);
        for(const auto &x : tmp)
        {
            mp[x.first] += x.second;
        }
        buff.push_back(tmp);
    }

    bool ok = true;

    for(Int i = 0; i < N; i++)
    {
        if(ok == false) break;
        for(const auto &x : buff[i])
        {
            mp[x.first] -= x.second;
        }

        for(const auto &x : buff[i])
        {
            if(mp[x.first] > 0)
            {
                ok = false;
                break;
            }
        }
    }

    if(ok)
    {
        cout << "pairwise coprime" << endl;
        return;
    }

    Int v = A.front();
    for(Int i = 0; i < N; i++)
    {
        v = gcd(v, A[i]);
    }
    if(v == 1)
    {
        cout << "setwise coprime" << endl;
        return;
    }
    cout << "not coprime" << endl;
}

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


Measured memory_bytes: 381444
import sys

def solve():
    input = sys.stdin.readline
    S = list(input().strip("\n"))
    K = int(input())
    N = len(S)
    head, tail, joint = 0, 0, 0
    inside = 0
    if S[0] == S[N-1]: #ジョイント部を考える必要がある場合
        isInitial = True
        current = S[0]
        currentLength = 1
        for i in range(1, N):
            if S[i] == current: currentLength += 1
            else:
                if isInitial: 
                    head = currentLength // 2
                    isInitial = False
                else: inside += currentLength // 2
                current = S[i]
                currentLength = 1
        if isInitial: #全て同じ文字の場合
            totalLength = N * K
            print(totalLength // 2)
        else:
            tail = currentLength // 2
            for i in range(N):
                if S[i] == current: currentLength += 1
                else: 
                    joint = currentLength // 2
                    break
            print(head + tail + joint * (K - 1) + inside * K)
    else:
        current = S[0]
        currentLength = 1
        for i in range(1, N):
            if S[i] == current: currentLength += 1
            else:
                inside += currentLength // 2
                current = S[i]
                currentLength = 1
        inside += currentLength // 2
        print(inside * K)   
    #print(head, tail, joint, inside)        
    return 0

if __name__ == "__main__":
    solve()

Measured memory_bytes: 3064
#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>;
const int INF = INT32_MAX;
const ll INFL = INT64_MAX;
const int mod = 1e9 + 7;

template <typename T>
void print_vec(vector<T> v) {
  for (T i : v) cout << i << " ";
  cout << endl;
}

int main() {
  int n, u, v;
  cin >> n >> u >> v;
  u--, v--;
  vector<vector<int> > to(n);
  rep(i, n - 1) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    to[a].push_back(b);
    to[b].push_back(a);
  }

  vector<int> dv(n, INF);
  dv[v] = 0;
  queue<int> q;
  q.push(v);
  while (!q.empty()) {
    int from = q.front();
    q.pop();
    for (int next : to[from]) {
      if (dv[next] != INF) continue;
      dv[next] = dv[from] + 1;
      q.push(next);
    }
  }

  int ans = dv[u];
  vector<int> du(n, INF);
  du[u] = 0;
  q.push(u);
  while (!q.empty()) {
    int from = q.front();
    q.pop();
    int nd = du[from] + 1;
    for (int next : to[from]) {
      if (du[next] != INF) continue;
      if (dv[next] <= nd) continue;
      ans = max(ans, dv[next]);
      // if (dv[next] == nd) continue;
      du[next] = nd;
      q.push(next);
    }
  }
  cout << ans - 1 << endl;

  return 0;
}

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

using namespace std;

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

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

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

	vector<int> dp(n + 1, INT_MAX);
	dp.at(0) = 0;
	dp.at(1) = h.at(0);
	for (int i = 1; i < n; i++)
	{
		dp.at(i) = dp.at(i - 1) + abs(h.at(i) - h.at(i - 1));
		if (1 < i)
		{
			chmin(dp.at(i), dp.at(i - 2) + abs(h.at(i) - h.at(i - 2)));
		}
	}

	cout << dp.at(n - 1) << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
const int INF = 2000000000;
using namespace std;

const int MAX_V = 100000;

class Node{
    public:
        bool isUsed;
        int prenum; //DFS????¨?????????????
        int parent; //DFS Tree???????????????
        int lowest; //min(?????????prenum, ?????????????????´????????????prenum, ??????????????????lowest)
        Node(){ this->isUsed = 0; }
};

int cnt = 1;
vector<Node> node(MAX_V);
vector<int> edge[MAX_V];

void dfs(int current, int prev){
    node[current].prenum = node[current].lowest = cnt;
    cnt++;

    node[current].isUsed = true;

    int next;
    rep(i,edge[current].size()){
        next = edge[current][i];
        if(not node[next].isUsed){
            node[next].parent = current;
            dfs(next, current);
            node[current].lowest = min(node[current].lowest, node[next].lowest);
        }else if(next != prev){
            node[current].lowest = min(node[current].lowest, node[next].prenum);
        }
    }
}

void art_points(int v){
    dfs(0, -1); // 0 == root

    set<int> ap;
    int np = 0;
    range(i,1,v){
        int p = node[i].parent;
        if(p == 0) np++;
        else if(node[p].prenum <= node[i].lowest) ap.insert(p);
    }
    if(np > 1) ap.insert(0);
    for(auto it:ap){
        cout << it << endl;
    }
}

int main(){
    int v, e;
    cin >> v >> e;

    rep(i,e){
        int s, t;
        cin >> s >> t;
        edge[s].emplace_back(t);
        edge[t].emplace_back(s);
    }
    art_points(v);
}

Measured memory_bytes: 8076