akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <assert.h>
#include <memory.h>
#include <time.h>
#include <bitset>
#include<iomanip>
 
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define ld long double
#define rep(i, l, r) for (int i = (l); i < (r); i++)
#define repb(i, r, l) for (int i = (r); i > (l); i--)
#define sz(a) (int)a.size()
#define fi first
#define se second
#define pii pair<int,int>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define mp(a, b) make_pair(a, b)
#define mt(a,b,c) make_tuple(a,b,c)
#define rank qwertyuio
#define next dfghjk
#define plus fsghsf
#define minus ytryr
#define pb push_back
#define debug(x) cerr<<#x<<": "<<(x)<<endl
using namespace std;
 
inline bool setmin(int &x, int y) { return (y < x) ? x = y, 1 : 0; }
inline bool setmax(int &x, int y) { return (y > x) ? x = y, 1 : 0; }
inline bool setmin(ll &x, ll y) { return (y < x) ? x = y, 1 : 0; }
inline bool setmax(ll &x, ll y) { return (y > x) ? x = y, 1 : 0; }
 
const int N = 100000;
const int inf = (int)1e9 + 1;
const ll big = (ll)1e18 + 1;
const int P = 239;
const int P1 = 31;
const int P2 = 57;
const int mod = (int)1e9 + 7;
const int mod1 = (int)1e9 + 9;
const int mod2 = 998244353;
const int mod3 = (int)1e6+3;
const ld eps = 1e-12;
const double pi = atan2(0, -1);
const int ABC = 26;
 
 
ll binary_search(vector<ll> arr,ll val,ll l,ll r){
    ll m=l+(r-l)/2;
    if(l>=r){
        return l;
    }
    if(val<arr[m]){
        return binary_search(arr,val,l,m);
    }
    else{
        return binary_search(arr,val,m+1,r);
    }
}//return position less than
ll binary_search2(vector<ll> arr,ll val,ll l,ll r){
    ll m=l+(r-l)/2;
    if(l>=r){
        return l;
    }
    if(val<=arr[m]){//changed here
        return binary_search2(arr,val,l,m);
    }
    else{
        return binary_search2(arr,val,m+1,r);
    }
}//return position less than or equal
ll power(ll x, ll y) 
{ 
    ll res = 1;      // Initialize result 
  
    x = x % mod;  // Update x if it is more than or 
                // equal to p 
  
    while (y > 0) 
    { 
        // If y is odd, multiply x with result 
        if (y & 1) 
            res = (res*x) % mod; 
  
        // y must be even now 
        y = y>>1; // y = y/2 
        x = (x*x) % mod; 
    } 
    return res; 
} 
ll modInverse(ll n) 
{ 
    return power(n, mod-2); 
}
int main()
{   ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin>>n;
    ll fact[n];
    fact[0]=1;
    ll x[n];
    int i;
    rep(i,0,n){
        if(i){
            fact[i]=(fact[i-1]*i)%mod;
        }
        cin>>x[i];
    }
    ll sum=0;
    rep(i,0,n-1){
        ll temp=((x[n-1]-x[i])*fact[n-1])%mod;
        temp=(temp*modInverse(i+1))%mod;
        sum=(sum+temp)%mod;
    }
    cout<<sum;

    return 0;
             
    
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
void input()
{ 
  #ifndef ONLINE_JUDGE 
  freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
  #endif
}
typedef long long int ll;
#define rep(i,a,b) for( ll i=a;i<b;i++)
#define rrep(i,a,b)for(ll i=a;i>=b;i--)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define f first
#define s second
#define mod 1000000007
bool compare(pair<int,int>a,pair<int,int>b)
{
  return a.f<b.f;
}
int main()
{
  //input();
  ios_base::sync_with_stdio(0);
    cin.tie(0);
 int n,ans=INT_MIN;
 cin>>n;
 int dp[n][3]={},arr[n][3]={};
 rep(i,0,n)cin>>arr[i][0]>>arr[i][1]>>arr[i][2];

 dp[0][0]=arr[0][0],dp[0][1]=arr[0][1],dp[0][2]=arr[0][2];
 rep(i,1,n)
 {
    rep(j,0,3)
    {
      int max1=INT_MIN;
      rep(k,0,3)
      {
        if(k!=j)
        {
          max1=max(dp[i-1][k]+arr[i][j],max1);
        }

      }
      dp[i][j]=max1;
      //cout<<dp[i][j]<<" ";
    }
    //cout<<endl;
 }
 rep(i,0,3)
 {
  ans=max(ans,dp[n-1][i]);
 }
cout<<ans<<endl;
}

///shubham gupta/


Measured memory_bytes: 2560
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/integer/common_factor.hpp>
#include <boost/integer/common_factor_rt.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>

using std::string;
using std::vector;
using std::set;
using std::multiset;
using std::unordered_set;
using std::map;
using std::multimap;
using std::unordered_map;
using std::pair;
using std::cin;
using std::cout;

typedef uintmax_t    ull;
typedef intmax_t     ll;
typedef uint64_t     ul;
typedef uint32_t     ui;
typedef uint8_t      uc;

typedef boost::multiprecision::number<boost::multiprecision::cpp_dec_float<1000>> cpp_dec_float_1000;

constexpr char CRLF  = '\n';
constexpr char SPACE = ' ';
constexpr char VECTOR_COUT_SEPARATOR = SPACE;
constexpr ll INF = 1000'000'007;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> std::ostream& operator<< (std::ostream& os, const std::vector<T>& vc) { for(auto it = vc.begin(); it != vc.end(); ++it) { if (std::next(it) == vc.end()) os << *it; else os << *it << VECTOR_COUT_SEPARATOR; } return os; }
template<class T1, class T2> inline std::ostream & operator<< (std::ostream & os, const std::pair<T1, T2> & p) { return os << p.first << ' ' << p.second; }

void solve(void)
{
  string N; cin >> N;
  auto it = N.find('9');
  auto ans = it != N.npos;
  cout << (ans ? "Yes" : "No") << CRLF;
  return;
}

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

  solve();

  return 0;
}


Measured memory_bytes: 256
// warm heart, wagging tail,and a smile just for you!
//
//                            ▒█████▒▒
//                             ██████████▒
//                             ▒████████████▒
//                            ██████████████████
//                           ████████████████████▒
//                          ▒██████████████████████▒
//                          ▒███████████████████████
//                      ▒████▒▒▒▒▒▒█████████████████▒
//                    ███▒▒▒▒▒▒██████████████████████▒▒▒
//                  ▒██▒▒███████████████████████▒▒▒▒▒██████
//                 ▒█████████████████████████▒▒▒▒▒▒█████████▒
//                 ▒█████████████████████▒▒▒▒▒▒██████████████
//                  ▒████         ████▒▒▒▒▒████         ████▒
//              ▒█████▒    ████    ▒▒▒▒███████    ████    ██████▒
//            ▒██▒▒▒▒▒    ██████    █████████    ██████    ██▒▒▒██▒
//           █████████   ████████   █████████   ████████   ▒▒▒▒█████
//          ▒█████████    ██████    ████████▒    ██████    █████████
//          ▒██████████    ████    █████▒▒▒▒▒▒    ████    ██████████
//           ████████████        ▒▒▒▒▒▒▒████████        ███████████▒
//       ▒██████████▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒███████████████████████████████████▒
//     ███▒▒▒▒▒▒▒▒▒▒▒▒█████████████████████████████████████████▒▒████████▒
//   ▒▒▒▒▒▒▒▒▒██████████████                         ███████▒▒▒▒███████████
//   █████████████████████████                     ███████▒▒▒██████████████▒
//   █████████████████████████████             ███████▒▒▒██████████████████▒
//   ██████████████████████████████████████████████████████████████████████
//    ██████████████████████████████████████████████████████████████████▒
//      ▒█████████████████▒▒▒▒▒▒▒██████████████████████████████████▒▒▒
//
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
const double EPS = 1e-9;
#define INF (1LL<<60)
#define D double
#define fs first
#define sc second
#define int long long
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for(int i = (b-1);i>=(a);--i)
#define REP(i,n)  FOR(i,0,(n))
#define RREP(i,n) RFOR(i,0,(n))
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x)  cout << #x << " = " << (x) << endl;
#define SP << " " << 
typedef pair<int,int> P;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

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

  int n,k;
  string s;
  cin >> n >> k >> s;

  int cnt = 0, ans = 0, num = 0;
  char c = s[0];
  REP(i,n){
    if(s[i] == c) cnt++;
    else{
      ans += cnt-1;
      cnt = 1;
      num++;
      c = s[i]; 
    }
  }

  ans += cnt-1; num++;

  REP(_,k){
    if(num == 1) break;
    if(num == 2) ans++,num--;
    else ans += 2, num -= 2;
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
#define pb   push_back
#define T int time;        scanf("%d", &time); while(time--)
    struct aray{
        ll a,b;
    };
//aray a[10000],b[100000];
int main(){
     //T{
      string s;
      cin>>s;
      if(s[s.size()-1] == 's')   s+="es";
    else if( s[s.size()-1] != 's' )    s+='s';

      cout<<s<<endl;


} 

Measured memory_bytes: 3636
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <numeric>

using namespace std;
typedef long long ll;

int main(){

  int a, b;
  cin >> a >> b;
  cout << max(a,b) + max((max(a,b) - 1), min(a, b)) << endl;

  return 0;
}


Measured memory_bytes: 256
//@author :  |< U $ |-|
#include<iostream>
#include<vector>
#include<math.h>
#include<map>
#define TakeInput freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
using namespace std;



int main(){
    
    #ifndef ONLINE_JUDGE
    TakeInput
    #endif
    
    int i,j,m,n,k;
    cin>>n;
    map<string , int> mp;
    string a[n];
    for(i=0;i<n;i++){
        cin>>a[i];
        mp[a[i]]++;
    }
    cout<<"AC x "<<mp["AC"]<<endl;
    cout<<"WA x "<<mp["WA"]<<endl;
    cout<<"TLE x "<<mp["TLE"]<<endl;
    cout<<"RE x "<<mp["RE"]<<endl;

}
 
 
 

Measured memory_bytes: 6728
#include <stdio.h>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))

int
main(int argc, char *argv[])
{
  int w, h, n, x[100], y[100], a[100];
  scanf("%d %d %d", &w, &h, &n);
  int max1 = 0, min2 = w, max3 = 0, min4 = h;
  for(int i = 0; i < n; i++){
    scanf("%d %d %d", &x[i], &y[i], &a[i]);
    switch(a[i]) {
    case 1:
      max1 = max(max1, x[i]);
      break;
    case 2:
      min2 = min(min2, x[i]);
      break;
    case 3:
      max3 = max(max3, y[i]);
      break;
    case 4:
      min4 = min(min4, y[i]);
      break;
    }
  }

  if(min2 < max1 || min4 < max3) printf("0\n");
  else printf("%d\n", (min2 - max1) * (min4 - max3));

  return 0;
      
}


Measured memory_bytes: 128
#include<stdio.h>
#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <iterator>
#include <list>
#include <map>     
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <iomanip>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define ll long long
#define ld long double
#define rep(a,t) for(int a=0;a<t;a++) 
#define forever while(true)
#define Sort(a) sort(a.begin(),a.end())
#define Reverse(a) reverse(a.begin(),a.end())
#define pb push_back
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int>a(n);
	rep(i, n) {
		cin >> a[i];
	}
	vector<int>s = a;
	Sort(s);
	int mid = s[s.size() / 2 - 1];
	for (int i = 0; i < n; i++) {
		if (a[i]<=mid) {
			cout << s[a.size() / 2 ] << endl;
			
		}
		else {
			cout << s[a.size() / 2-1] << endl;
		}
	}
	return 0;
}

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

class UnionFind {
private:
    vector<int> par;

public:
    UnionFind(int n){
        par = vector<int>(n,-1);
    }

    int root(int x) {
        if (par[x] < 0) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry) return;
        if (size(rx) < size(ry)) swap(rx,ry);
        par[rx] += par[ry];
        par[ry] = rx;
    }

    bool same(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }

    int size(int x) {
        return -par[root(x)];
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    vector<int> A(m),B(m);
    vector<ll> C(m);
    for(int i = 0; i < m; i++)
    {
        cin >> A[i] >> B[i];
        A[i]--;
        B[i]--;
    }

    UnionFind U(n);
    C[m-1] = (ll)n*(n-1)/2;

    for(int i = m-1; i >= 1; i--)
    {
        C[i-1] = C[i];
        if (!U.same(A[i],B[i])) {
            C[i-1] -= (ll)U.size(A[i])*U.size(B[i]);
        }
        U.unite(A[i],B[i]);
    }

    for(int i = 0; i < m; i++)
    {
        cout << C[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 3328
S = input()
T = input()
 
N = len(S)
M = len(T)
l = []
# Sから順にM文字切り出し、切り出した文字列とTのハミング距離における最小値を求める
for i in range(N+1-M):
  dis = M
  for j in range(M):
    if S[i:i+M][j] == T[j]:
      dis -= 1
  l.append(dis)
  
print(min(l))

Measured memory_bytes: 8988
import sys
sys.setrecursionlimit(10**6)


N = int(input())

es = [[] for _ in range(N)]


for i in range(N-1):
    a,b = map(int, input().split())
    es[a-1].append((b-1, i))

# 辺の色
ans = [0] * (N-1)


def solve(now, prev_color):
    # 小さいものから
    color = 1
    for b,i in es[now]:
        # nowが繋がっている辺（nowとnowの親を繋ぐ辺）と同じ色なら＋１
        if color == prev_color:
            color += 1
        # i番目の辺に塗る
        ans[i] = color
        # bの子とつながる辺についてみていく
        solve(b, color)
        # 次のbで今のｂと色が被らないように＋１
        color += 1

# 
solve(0,0)



print(max(ans))
print(*ans, sep="\n")

Measured memory_bytes: 69148
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
    int n;
    while(~scanf("%d",&n)){
        int a[2010]={0};
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
        }
        sort(a,a+n);
        int ans=0;
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                for(int k=i+1;k<n;k++){
                    if(a[k]<a[i]+a[j]) ans++;
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}


Measured memory_bytes: 128
use std::io;

fn procon_read<T: std::str::FromStr>() ->  Vec<T> {
	let mut buf = String::new();
	io::stdin().read_line(&mut buf).expect("");
	let iter = buf.split_whitespace();
	let mut v: Vec<T> = Vec::new();
	for i in iter {
		v.push(i.parse().ok().unwrap());
	}
	v
}

fn main() {
	let v:Vec<i32> = procon_read();
	let a = v[0];
	let b = v[1];
	println!("{}", ((b-a) + 1)*(b-a)/2 - b);
}

Measured memory_bytes: 4476
#include <bits/stdc++.h>
#define ri register int 
using namespace std;
template <class T>void read(T &x){
  x=0;int ne=0;char c;
  while(!isdigit(c=getchar()))ne=c=='-';
  x=c-48;
  while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
  x=ne?-x:x;
  return ;
} 
int n,m,d;
int main(){
  read(n),read(m),read(d);
  if(d==0)printf("%.10Lf\n",(long double)(m-1)/n);
  else if(n<=d)printf("0.0000000\n");
  else printf("%.10Lf\n",(long double)(1.00*2*(n-d)*(m-1))/n/n);
  return 0;
}

Measured memory_bytes: 256
# NはSの個数、MはCの個数
N, M = map(int, input().split())

# 既存のSを消費しきれない場合
if M < 2 * N:
    # Cの個数のみでSccの数が決まる
    print(M // 2)

# 既存のSを消費し切れる場合
else:
    ans_1 = N
    M = M - 2 * N
    ans_2 = M // 4
    print(ans_1 + ans_2)


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

#define el '\n'
#define ll long long

const int MAXN = 105;
const int MOD = 1e9+7;
int dp[100005]; // byknya cara membagi candy di i
int a[MAXN];

void tambah(int& a, int b){
  a += b;
  if(a>=MOD) a -= MOD;
}

void kurang(int& a, int b){
  a -= b;
  if(a<0) a += MOD;
}

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

  int n, k;
  cin >> n >> k;
  for(int i = 0; i < n; i++){
    cin >> a[i];
  }

  dp[0] = 1;
  for(int i = 0; i < n; i++){
    vector<int> pref(k+1);
    for(int candy = k; candy >= 0; candy--){
      int l = candy+1;
      int r = candy+a[i];
      r = r > k ? k : r;
      if(l<=r){
        tambah(pref[l],dp[candy]);
        if(r+1 <= k) kurang(pref[r+1],dp[candy]);       
      }

    }

    int sum_now = 0;
    for(int i = 0; i <= k; i++){
      tambah(sum_now,pref[i]);
      tambah(dp[i],sum_now);
    }
  }
  cout << dp[k] << el;

  return 0;
}

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

int main() {
  string S;
  cin >> S;
  reverse(S.begin(), S.end());

  vector<string> lst = { "dream", "dreamer", "erase", "eraser" };
  for (int i = 0; i < 4; i++) reverse(lst.at(i).begin(), lst.at(i).end());

  bool ans_flag = true;

  for (int i = 0; i < S.size();) {
    bool canDivide = false;
    for (int j = 0; j < 4; j++) {
      string t = lst.at(j);
      if (S.substr(i, t.size()) == t) {
        canDivide = true;
        i += t.size();
      }
    }
    if (!canDivide) {
      ans_flag = false;
      break;
    }
  }

  if (ans_flag) cout << "YES" << endl;
  else cout << "NO" << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h> 
#include<cmath>
#define pb push_back
#define ll long long
#define ull unsigned long long
#define deb(x) cerr<<#x<<" "<<x<<"\n"
#define debi cerr<<"hey sparky\n"
#define x first
#define y second
#define nax 3e5+2
using namespace std;

int main() 
{ 	
	int k,n;
	cin>>k>>n;
	vector<int> v(n);
	for(int i=0;i<n;i++){
		cin>>v[i];
		
	}
	int ma = INT_MIN;
	for(int i =1;i<n;i++){
		int temp = v[i]-v[i-1];
		if(temp > ma){
			ma = temp;
		}
		
	}
	int val = (k+v[0])- v[n-1];
	if(val > ma){
		ma = val;
	}
	int ans = k -ma ;
	
	cout<<ans;
	return 0;
} 


Measured memory_bytes: 1024
#include<iostream>
    #include<stdio.h>
    //#include <bits/stdc++.h>
    #include<vector>
    #include<float.h>
    #include<iomanip>
    #include<algorithm>
    #include<string>
    #include<cstring>
    #include<math.h>
    #include<sstream>
    #include<set>
    #include<map>
    #include<queue>

    #define INF 1e9
    #define rep(i,n)for(int i=0;(i)<(int)(n);i++)
    #define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
    #define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
    #define vec(type,n) vector<type>(n)
    #define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))

    using namespace std;
    using ll = long long;

    int main(){
      string s,t;
      cin>>s>>t;
      bool f = false;
      reverse(s.begin(),s.end());
      reverse(t.begin(),t.end());
      rep(i,s.size()-t.size()+1){
        string s2 = s.substr(i,t.size());
        rep(j,t.size()){
          if(s2[j] != '?' && s2[j] != t[j])break;
          if(j == t.size()-1){
            f = true;
            s.replace(i,t.size(),t);
          }
        }
        if(f)break;
      }
      reverse(s.begin(),s.end());
      if(f){
        rep(i,s.size())if(s[i] == '?')s[i] = 'a';
        cout<<s<<endl;
        return 0;
      }
      else cout<<"UNRESTORABLE"<<endl;
      return 0;
    }


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

int main()
{
    int ans_a[100],ans_b[100];
    int hit,blow;
    
    while (cin>>ans_a[0]>>ans_a[1]>>ans_a[2]>>ans_a[3]>>ans_b[0]>>ans_b[1]>>ans_b[2]>>ans_b[3]) {
        hit=0,blow=0;
        for (int i=0; i<4; i++) {
            if (ans_a[i]==ans_b[i]) {
                hit++;
            }
            else{
            for (int j=0; j<4; j++) {
                if(ans_a[i]==ans_b[j]) {
                    blow++;
                }
            }
            }
        }
        cout<<hit<<" "<<blow<<endl;
    }
    
    return 0;
}

Measured memory_bytes: 1160
use proconio::input;

fn solve() -> usize {
    input! {
        mut n: usize,
        mut x: usize,
        m: usize,
    }

    let mut used = vec![false; m];

    let mut ans = 0usize;
    while !used[x] {
        if n == 0 {
            return ans;
        }
        used[x] = true;
        ans += x;
        x = x * x % m;
        n -= 1;
    }

    let mut used = vec![false; m];
    let mut sum = 0;
    let mut le = 0;
    while !used[x] {
        if n == 0 {
            return ans + sum;
        }
        used[x] = true;
        le += 1;
        sum += x;
        x = x * x % m;
        n -= 1;
    }

    let t = n / le;
    n -= t * le;
    ans += sum * t + sum;

    while n > 0 {
        ans += x;
        x = x * x % m;
        n -= 1;
    }

    ans
}

fn main() {
    println!("{}", solve());
}


Measured memory_bytes: 2308
from collections import deque
from typing import Tuple


def dfs(root: int) -> Tuple[int, int]:
    global edges
    visited = [False] * n
    queue: deque = deque()
    queue.append((0, root))
    longest = (-1, -1)

    while queue:
        total_weight, node = queue.pop()
        if visited[node]:
            continue
        visited[node] = True
        longest = max(longest, (total_weight, node))
        for w, t in edges[node]:
            if not visited[t]:
                queue.append((total_weight + w, t))

    return longest


if __name__ == "__main__":
    n = int(input())
    edges = [set() for _ in range(n)]  # type: ignore

    for _ in range(n - 1):
        s, t, w = map(lambda x: int(x), input().split())
        edges[s].add((w, t))
        edges[t].add((w, s))

    _, ln = dfs(0)  # Find the deepest node.
    ans, _ = dfs(ln)  # Traverse from the deepest node.
    print(ans)



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

typedef long long ll;

ll func(int x, int y, int z) {
    ll a;
    a = x*x + y*y + z*z + x*y + y*z + z*x;
    return a;
}

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

    map<ll, ll> mp;

    ll v;
    bool check;
    for (int x = 1; func(x, x, x) <= N; x++) {
        check = false;
        for (int y = x; y <= 1000; y++) {
            for (int z = y; z <= 1000; z++) {
                v = func(x, y, z);
                if (v > N) {
                    check = true;
                    break;
                } else {
                    if (x == y && y == z) {
                        mp[v]++;
                    } else if (x == y || y == z || z == x) {
                        mp[v] += 3;
                    } else if (x != y && y != z && z != x) {
                        mp[v] += 6;
                    }
                }
            }
            if (func(x, y+1, y+1) > N) {
                break;
            }
        }
    }


    for (int i = 1; i <= N; i++) {
        cout << mp[i] << endl;
    }
}


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




string _s; int _n; int sa_k;
vector<int> Rank, tmp, sa, lcp;
bool cmp_sa(int i, int j) {
	if (Rank[i] != Rank[j]) return Rank[i]<Rank[j];
	return (i + sa_k <= _n ? Rank[i + sa_k] : -1)<(j + sa_k <= _n ? Rank[j + sa_k] : -1);
}
void construct_sa() {
	for (int i = 0; i <= _n; i++) { sa[i] = i; Rank[i] = i<_n ? _s[i] : -1; }
	for (sa_k = 1; sa_k <= _n; sa_k *= 2) {
		sort(sa.begin(), sa.end(), cmp_sa); tmp[sa[0]] = 0;
		for (int i = 1; i <= _n; i++) tmp[sa[i]] = tmp[sa[i - 1]] + (cmp_sa(sa[i - 1], sa[i]) ? 1 : 0);
		for (int i = 0; i <= _n; i++) Rank[i] = tmp[i];
	}
}
void construct_lcp() {
	for (int i = 0; i <= _n; i++) Rank[sa[i]] = i;
	int h = 0; lcp[0] = 0;
	for (int i = 0; i<_n; i++) {
		int j = sa[Rank[i] - 1]; if (h>0) h--;
		for (; j + h<_n&&i + h<_n; h++) if (_s[j + h] != _s[i + h]) break; lcp[Rank[i] - 1] = h;
	}
}
void init(string s) {
	_s = s;	_n = s.length();
	Rank = vector<int>(_n + 1); tmp = vector<int>(_n + 1);
	sa = vector<int>(_n + 1); lcp = vector<int>(_n + 1);
	construct_sa(); construct_lcp();
}
bool chk(string s) {
	int lo = 0, hi = _n + 1;
	while (lo + 1 != hi) {
		int md = (lo + hi) / 2;
		
		string t = _s.substr(sa[md], s.length());
		if (s < t) hi = md;
		else lo = md;
	}
	
	string t = _s.substr(sa[lo], s.length());
	return s == t;
}
//-----------------------------------------------------------------------------------
int N;
string S[101010];
//-----------------------------------------------------------------------------------
#define rrep(i,a,b) for(int i=a;i>=b;i--)
string nxt(string x) {
	int carry = 1;
	rrep(i, x.length() - 1, 0) {
		int n = x[i] - 'a' + carry;
		carry = 0;
		if (26 <= n) {
			n %= 26;
			carry = 1;
		}
		x[i] = 'a' + n;
	}
	if (carry) x = "a" + x;
	return x;
}
//-----------------------------------------------------------------------------------
int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> N; rep(i, 0, N) cin >> S[i];

	string SS = "";
	rep(i, 0, N) SS += "#" + S[i];
	init(SS);

	string ans = "a";
	while (chk(ans)) ans = nxt(ans);
	cout << ans << endl;
}

Measured memory_bytes: 16528
#include <bits/stdc++.h>
using namespace std;
#define mp(a, b) make_pair(a, b)
#define lowbit(x) (x & (-x))
#define ls (rt << 1)
#define rs (rt << 1 | 1)
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 10;
int n, Max;
string s;
map<string, int> m; 
int main()
{
	cin >> n;
	for(int i = 1; i <= n; ++i)
	{
		cin >> s;
		m[s]++;
		Max = max(Max, m[s]);
	}
	for(auto v : m)
		if(v.second == Max)
			cout << v.first << endl;
	return 0;
}

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

using namespace std;

typedef long long ll;

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    int a, b, c;
    cin >> a >> b >> c;
    if (a + b + c >= 22) {
        cout << "bust\n";
    } else {
        cout << "win\n";
    }
    return 0;
}


Measured memory_bytes: 256
# include <iostream>
# include <algorithm>
#include <array>
# include <cassert>
#include <cctype>
#include <climits>
#include <numeric>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <tuple>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
# include <chrono>
# include <random>
# include <limits.h>
# include <unordered_map>
# include <unordered_set>
# include <deque>
# include <cstdio>
# include <cstring>
#include <stdio.h>
#include<time.h>
#include <stdlib.h>
#include <cstdint>
#include <cfenv>
#include<fstream>
//#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const long long MOD = 1000000000 + 7;//1000000000 + 7 998244353 924844033 1000000000 + 9;
constexpr long long INF = 1LL << 60;//numeric_limits<LL>::max();
const double PI = acos(-1);
#define fir first
#define sec second
#define thi third
#define debug(x) cerr<<#x<<": "<<x<<'\n'
typedef pair<LL, LL> Pll;
typedef pair<double, double> Dll;
typedef pair<LL, pair<LL, LL>> Ppll;
typedef pair<LL, pair<LL, bitset<100001>>> Pbll;
typedef pair<LL, pair<LL, vector<LL>>> Pvll;
typedef pair<LL, LL> Vec2;
struct Tll { LL first, second, third; };
struct Fll { LL first, second, third, fourth; };
typedef pair<LL, Tll> Ptll;
#define rep(i,rept) for(LL i=0;i<rept;i++)
#define Rrep(i,mf) for(LL i=mf-1;i>=0;i--)
void YN(bool f) {
	if (f)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}
void yn(bool f) {
	if (f)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}
struct Edge { LL to, cost; };
struct edge {
	LL from, to, cost;
};
vector<vector<LL>>g,rev;
vector<edge>ed;
vector<Pll>pv;
set<LL>st;
map<Pll, LL>ma;
int di[4][2] = { { 0,1 },{ 1,0 },{ 0,-1 },{ -1,0 } };
string str, ss;
bool f;
LL n, m, s, t, h, w, k, q, p, ans, sum, cnt, a[200000], b[200000];
int main() {
	cin >> n;
	g.resize(n);
	if (n % 2) {
		rep(i, n) {
			rep(j, n) {
				if (i >= j)continue;
				if (i + j + 2 != n) {
					g[i].push_back(j);
				}
			}
		}
	}
	else {
		rep(i, n) {
			rep(j, n) {
				if (i >= j)continue;
				if (i + j + 2 != n+1) {
					g[i].push_back(j);
				}
			}
		}
	}
	rep(i, n) {
		rep(j, g[i].size()) {
			cnt++;
		}
	}
	cout << cnt << endl;
	rep(i, n) {
		rep(j, g[i].size()) {
			cout << i + 1 << " " << g[i][j] + 1 << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 384
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int A[] = new int[N];
        for(int i=0;i<A.length;i++){
            A[i] = sc.nextInt();
        }
        int count = 0;
        boolean flag = true;
        while(flag){
            flag = false;
            for(int j = N-1; j > 0; j--){
                if(A[j] < A[j-1]) {
                    int tmp;
                    tmp = A[j-1];
                    A[j-1] = A[j];
                    A[j] = tmp;
                    count++;
                    flag = true;
                }
            }
        }
        for(int i = 0;i < A.length-1;i++){
            System.out.printf("%d ",A[i]);
        }
        System.out.println(A[N-1]);
        System.out.println(count);
    }
}


Measured memory_bytes: 26520
/* {{{ */
use std::io::*;
use std::str::FromStr;

struct Scanner<R: Read> {
    reader: R,
}

impl<R: Read> Scanner<R> {
    fn new(r: R) -> Scanner<R> {
        Scanner { reader: r }
    }
    fn read<T: FromStr>(&mut self) -> T {
        let token = self
            .reader
            .by_ref()
            .bytes()
            .map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        token.parse::<T>().ok().unwrap()
    }
}
/* }}} */

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);
    let n: usize = sc.read();
    let mut v = vec![vec![None;n];n];
    for i in 0..n {
        let a: usize = sc.read();
        for _ in 0..a {
            let x = sc.read::<usize>() - 1;
            let y = if sc.read::<usize>() == 0 {false} else {true};
            v[i][x] = Some(y);
        }
    }
    let mut res = 0;
    for b in 0..(1u64 << n) {
        let mut h = vec![false;n];
        for i in 0..n {
            if b & (1 << i) != 0 {
                h[i] = true;
            }
        }
        let mut ok = true;
        for i in 0..n {
            if !h[i] { continue; }
            for j in 0..n {
                if let Some(y) = v[i][j] {
                    if h[j] != y {
                        ok = false;
                        break;
                    }
                }
            }
        }
        if ok {
            let cnt = h.iter().filter(|b| **b).count();
            res = std::cmp::max(res, cnt);
        }
    }
    println!("{}", res);
}
/* vim:set foldmethod=marker: */


Measured memory_bytes: 4352
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    long[] a = new long[n];
    HashMap<Long, Integer> map = new HashMap<Long, Integer>();
    for(int i = 0; i < n; i++) {
      a[i] = sc.nextLong();
      if(map.containsKey(a[i])) {
        map.put(a[i], map.get(a[i]) + 1);
      } else {
        map.put(a[i], 1);
      }
    }
    ArrayList<Long> edge = new ArrayList<Long>();
    for(long key : map.keySet()) {
      if(map.get(key) > 1) edge.add(key);
    }
    Collections.sort(edge);
    long ans = 0;
    if(edge.size() > 1) {
      if(map.get(edge.get(edge.size() - 1)) >= 4) {
        ans = edge.get(edge.size() - 1) * edge.get(edge.size() - 1);
      } else {
        ans = edge.get(edge.size() - 1) * edge.get(edge.size() - 2);
      }
    } else if(edge.size() == 1) {
      if(map.get(edge.get(0)) >= 4) ans = edge.get(0) * edge.get(0);
    }
    System.out.println(ans);
  }
}

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

using namespace std;
typedef long long ll;

#define MOD (long long)(1e9+7)
#define REP(i,n) for(ll i = 0; i < n; i++)
#define REP1(i,n) for(ll i = 1; i <= n; i++)

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

void solve()
{
  ll a, b; cin >> a >> b;

  if((a <= 0 && b >= 0) || a == 0 || b == 0) {
    cout << "Zero" << endl;
    return;
  }

  if(a > 0 ) {
    cout << "Positive" << endl;
    return ;
  }
  if((b - a + 1) % 2 == 0) {
    cout << "Positive" << endl;
  } else {
    cout << "Negative" << endl;
  }
  
  //Positive を、負ならば Negative を、0 ならば Zero を出力せよ。
}


int main(void)
{
  // ll t; cin >> t; REP(i, t)
  solve();
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdlib>
#include<vector>
#include<algorithm>
#include<functional>


#define ll long long int

using namespace std;

int main() {
  string s;
  cin >> s;
  int n = atoi(s.c_str());

  int sn = 0;
  for (int i = 0; i < s.size(); i++) {
    string tmp = s.substr(i, 1);
    sn += atoi(tmp.c_str());
  }

  if (n%sn == 0) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long w = sc.nextLong();
        long h = sc.nextLong();
        long x = sc.nextLong();
        long y = sc.nextLong();
        if (x == (double) w / 2 && y == (double) h / 2) {
            System.out.println((double) w * h / 2 + " " + 1);
            return;
        }
        System.out.println((double) w * h / 2 + " " + 0);
    }

}


Measured memory_bytes: 23764
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;
typedef pair<int,int> Paint;
#define rep(i,q) for(int i = 0; (q) > i; i++)
int main(){
  int n;cin>>n;
  float sm = 0;
  rep(i,n){
    float m;
    string s;
    cin >> m >> s;
    if(s == "JPY")sm += m;
    else sm += 380000 * m;
  }
  cout << sm << endl;
}

Measured memory_bytes: 384
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    N = int(input())
    if N==1:
        print('a')
    else:
        q = ['a']
        for _ in range(N - 1):
            nq = []
            for j in q:
                for k in range(ord('a'), ord(max(j)) + 2):
                    nq.append(j + chr(k))
            q=nq

        print(*q,sep='\n')

resolve()

Measured memory_bytes: 63324
def getminLT(i):
  if LT[i] == i:
    return i
  else:
    return getminLT(LT[i])

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

D = []
for i in range(H):
  D.append(input())

M = [[0] * W for i in range(H)]
LT = [0]
for i in range(H):
  for j in range(W):
    if i == 0 and j == 0:
      continue
    flag = False
    if i != 0:
      if D[i][j] != D[i-1][j]:
        M[i][j] = M[i-1][j]
        flag = True
    if j != 0:
      if D[i][j] != D[i][j-1]:
        M[i][j] = M[i][j-1]
        if flag == True:
          
          LT[max(getminLT(M[i-1][j]), getminLT(M[i][j-1]))] = LT[min(getminLT(M[i][j-1]), getminLT(M[i-1][j]))]
        flag = True
    if flag == False:
        M[i][j] = len(LT)
        LT.append(len(LT))
for i in range(len(LT)):
  LT[i] = getminLT(LT[i])
  
L = [[] for i in range(len(LT))]
for i in range(H):
  for j in range(W):
  	L[LT[M[i][j]]].append((i, j))
#print(M)
#print(LT)
#print(L)
cnt = 0
for i in L:
  E = 0
  A = 0
  for j in i:
    if (j[0] + j[1]) % 2 == 0:
      E += 1
    else:
      A += 1
  cnt += E * A
print(cnt)


Measured memory_bytes: 40876
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define show(x) cout << #x << " = " << (x) << endl;
using namespace std;
using ll = long long;
using pii = pair<int,int>;
int main(){
    string s;
    cin >> s;
    int w;
    cin >> w;
    rep(i,s.size()){
        if(i%w){
            
        }else{
            cout << s[i];
        }
    }
    cout << endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <array>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <functional>

using namespace std;
using lli = long long int;
using ll = long long;

int main() {
    lli N, K;
    cin >> N >> K;

    vector<int> h(N);
    for (int i = 0; i < N; ++i) {
        cin >> h[i];
    }

    lli counter = 0;
    for (int i = 0; i < N; ++i) {
        if (h[i] >= K) {
            ++counter;
        }
    }

    cout << counter << endl;
    return 0;
}


Measured memory_bytes: 640
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>

using namespace std;

typedef long long ll;

mt19937 rnd(228);

const int N = (1 << 15);
const int M = 17;
const int MOD = 1e9 + 7;

inline int add(int a, int b)
{
    a += b;
    if (a >= MOD) a -= MOD;
    if (a < 0) a += MOD;
    return a;
}

inline int mul(int a, int b)
{
    return (a * (ll) b) % MOD;
}

int dp[M][N];
int prec[N];
int g[M];
int mem[20000000];

int main()
{
#ifdef ONPC
    freopen("a.in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a] |= (1 << b);
    }
    int lim = (1 << n);
    for (int mask = 1; mask < lim; mask++)
    {
        prec[mask] = prec[mask - (mask & -mask)] + 1;
    }
    int it = 0;
    for (int mask = 0; mask < lim; mask++)
    {
        if (mask == lim - 1)
        {
            continue;
        }
        else
        {
            int ret = (lim - 1) ^ mask;
            for (int sm = ret; sm > 0; sm = (sm - 1) & ret)
            {
                if (((sm >> 0) & 1) && ((sm >> 1) & 1))
                {
                    continue;
                }
                int ans = 1;
                for (int i = 0; i < n; i++)
                {
                    if ((sm >> i) & 1) continue;
                    if (!((mask >> i) & 1))
                    {
                        ans = mul(ans, (1 << prec[g[i] & sm]) - 1);
                    }
                    else
                    {
                        ans = mul(ans, (1 << prec[g[i] & sm]));
                    }
                }
                mem[it++] = ans;
            }
        }
    }
    int ans = 0;
    dp[0][0] = 1;
    for (int gr = 0; gr <= n + 1; gr++)
    {
        int it = 0;
        for (int mask = 0; mask < lim; mask++)
        {
            if (mask == lim - 1)
            {
                ans = add(ans, dp[gr][mask]);
            }
            else
            {
                if (gr == n + 1)
                {
                    break;
                }
                int ret = (lim - 1) ^ mask;
                for (int sm = ret; sm > 0; sm = (sm - 1) & ret)
                {
                    if (((sm >> 0) & 1) && ((sm >> 1) & 1))
                    {
                        continue;
                    }
                    dp[gr + 1][mask | sm] = add(dp[gr + 1][mask | sm], mul(dp[gr][mask], mem[it++]));
                }
            }
        }
    }
    cout << ans << '\n';
}


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

int main(){
    long long N, left=0, right=0, ans=2e9;
    cin >> N;
    vector<long long> a(N);
    for(int i=0; i<N; i++){
	cin >> a[i];
	right += a[i];
    }

    for(int i=0; i<N-1; i++){
	left += a[i];
	right -= a[i];
	ans = min(ans, abs(right-left));
    }

    cout << ans << endl;


}



Measured memory_bytes: 1792
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0]*n
    def find(self, x):
        if x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def check(self, x, y):
        if self.find(x) == self.find(y):
            return True
        else:
            return False
    def union(self, x, y):
        parx = self.find(x)
        pary = self.find(y)
        if self.rank[parx] < self.rank[pary]:
            self.par[parx] = pary
        else:
            self.par[pary] = parx
            if self.rank[pary] == self.rank[parx]:
                self.rank[parx] += 1
n,q = map(int, input().split())
G = UnionFind(n)
ans = []
for _ in range(q):
    c,x,y = map(int, input().split())
    if c == 0:
        G.union(x,y)
    elif c == 1:
        if G.check(x,y) == True:
            ans.append(1)
        else:
            ans.append(0)
    # print(G.par,G.rank)
    # if c == 1:
    #     print(G.find(x),G.find(y),G.check(x,y))

for i in range(len(ans)):
    print(ans[i])
    
        


Measured memory_bytes: 7184
#include <bits/stdc++.h>
const int INF=1e9;
const int MOD=1e9+7;
//const int MOD=998244353;
const long long LINF=1e18;
using namespace std;
#define int long long
#define fin {cout<<"-1"<<endl;return 0;}
//template
struct Fordfulkerson{
  const int INF = 1 << 28;
  struct edge{
    int to,cap,rev;
    edge(){}
    edge(int to,int cap,int rev):to(to),cap(cap),rev(rev){}
  };

  int n;
  vector<vector<edge> > G;
  vector<int> used;

  Fordfulkerson(){}
  Fordfulkerson(int sz):n(sz),G(n),used(n){}

  void add_edge(int from,int to,int cap){
    G[from].push_back(edge(to,cap,G[to].size()));
    // undirected
    G[to].push_back(edge(from,cap,G[from].size()-1));
    // directed
    //G[to].push_back(edge(from,0,G[from].size()-1));
  }

  int dfs(int v,int t,int f){
    if(v==t) return f;
    used[v]=true;
    for(int i=0;i<(int)G[v].size();i++){
      edge &e = G[v][i];
      if(!used[e.to] && e.cap > 0 ){
        int d=dfs(e.to,t,min(f,e.cap));
        if(d>0){
          e.cap-=d;
          G[e.to][e.rev].cap+=d;
          return d;
        }
      }
    }
    return 0;
  }

  int flow(int s,int t,int lim){
    int fl=0;
    for(;;){
      fill(used.begin(),used.end(),0);
      int f=dfs(s,t,lim);
      if(f==0) return fl;
      fl+=f;
      lim-=f;
    }
  }

  int flow(int s,int t){
    return flow(s,t,INF);
  }

};
//main
signed main(){
  int H,W;cin>>H>>W;
  std::vector<string> b(H);
  for(int i=0;i<H;i++)cin>>b[i];
  typedef pair<int,int> P;
  P s,t;
  for(int i=0;i<H;i++)for(int j=0;j<W;j++)if(b[i][j]=='S')s=P(i,j);
  for(int i=0;i<H;i++)for(int j=0;j<W;j++)if(b[i][j]=='T')t=P(i,j);
  if(s.first==t.first||s.second==t.second)fin;
  Fordfulkerson fl(302);
  fl.add_edge(300,s.first,LINF);
  fl.add_edge(300,s.second+150,LINF);
  fl.add_edge(301,t.first,LINF);
  fl.add_edge(301,t.second+150,LINF);
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(b[i][j]=='o'){
        fl.add_edge(i,j+150,1);
      }
    }
  }
  cout<<fl.flow(300,301)<<endl;
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
#define int long long
#define float long double
#define PB push_back
#define MP make_pair
#define ss second
#define ff first
#define PI 3.14159265
#define fastrack ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
const int M = 2007, mod = 998244353;

signed main(){
    fastrack;
    int tt = 1;
    //cin >> tt;
    while(tt--){
        int w, s;
        cin >> s >> w;
        if(w >= s)
            cout << "unsafe" << "\n";
        else
            cout << "safe" << "\n";
    }
    return 0;
}


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

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<ll> vll;

#define PI (2*acos(0.0))
#define eps 1e-9
#define pb push_back
#define endl "\n"
#define watch(x) cout << (#x) << " is " << (x) << endl;
#define show(v) for(int fi = 0; fi < v.size(); fi++) cout << v[fi] << " "; cout << endl;
#define showpair(v) for(int fi = 0; fi < v.size(); fi++) cout << v[fi].first << " " << v[fi].second << endl;
#define ff first
#define ss second
#define fu cout << "lol" << endl;
#define precision(n) cout << fixed << setprecision(n);
#define lb lower_bound
#define up upper_bound
#define vscan for(i = 0;i<n;i++){cin>>in; v.pb(in);}
#define all(a) a.begin(), a.end()
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define mem(a,val) memset(a,val,sizeof(a))
#define loop(i,n) for(i = 0; i < n; i++)
#define TC() ull T; cin>>T; while(T--)
#define IN(x) {scanf("%d",&x);}
#define LL(x) {scanf("%lld",&x);}
#define CC(x) {scanf("%c",&x);}
#define pfl(x) printf("%d\n",x)
#define pfll(x) printf("%lld\n",x)
#define newl puts("")
#define space printf(" ")
#define MOD 1000000007
#define speed ios_base::sync_with_stdio(false); cin.tie(NULL);


int main()
{
    int i = 0, j = 0, cs = 0, in;
    string s; cin>>s;
    if(s[0] == '7' || s[1] == '7' || s[2] == '7') cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3624
#include <stdlib.h>
#include <cmath>
#include <cstdio>
#include <cstdint>
#include <string>
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
using namespace std;
using ll = long long;

int main(){
  string T;
  cin >> T;

  bool pre_P=false;
  bool flag=false;
  ll count=0;
  for(int i=0;i<T.size();i++){
    if(T.at(i)=='P'){
      pre_P=true;
      if(flag==true){
	T.at(i-1)='D';
	count++;
	flag=false;
      }
    }
    else if(T.at(i)=='D'){
      count++;
      if(pre_P==true) count++;
      pre_P=false;
      if(flag==true){
	T.at(i-1)='P';
	count++;
	flag=false;
      }
    }
    else if(T.at(i)=='?'){
      if(flag==true){
	T.at(i-1)='P';
	T.at(i)='D';
	count+=2;
	pre_P=false;
	flag=false;
	continue;
      }
      if(pre_P==true){
	T.at(i)='D';
	count+=2;
	pre_P=false;
      }
      else{
	if(i==T.size()-1){
	  T.at(i)='D';
	  count++;
	  continue;
	}
	flag=true;
      }
      pre_P=false;
    }
  }
  

  cout << T << endl;
  
  return 0;
}


Measured memory_bytes: 3720
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		try(Scanner sc = new Scanner(System.in)) {
			double a = sc.nextDouble();
			double b = sc.nextDouble();
			double x = sc.nextDouble();
			
			double h = x / Math.pow(a, 2);
			
			//傾きと高さの関係を考える
			double tan = 2 * ( b - h) / a;			
			
			//整合性をチェック
//			System.out.println("h = " + h);
//			System.out.println("tan = " + tan);
//			System.out.println("dh = " + a * tan / 2);
			
			double dh = a * tan / 2;
			
			if ( dh > h ) {
				//三角形になっている
				//c * ctan / 2 = a * h && ctan = b
				//c * b /2 = a * h
				// c = 2 * a * h / b
				// tan = b^2 / 2 * a * h
				tan = Math.pow(b, 2) / (2 * a * h);
			}

			double result = Math.atan(tan) * 180 / Math.PI;
			System.out.println(result);
		}
	}
}

Measured memory_bytes: 24532
H,W = map(int,input().split())
#print(H)
ans = 1


if H*W%2 == 0:
    ans = int(H*W/2)
else:
    ans = int(H*W//2 + 1)
#output
if H == 1:
    ans = 1
if W == 1:
    ans = 1
print(ans)

Measured memory_bytes: 2940
#include<stdio.h>
int main(void){
  int r,g,b,n,cnt = 0;
  scanf("%d %d %d %d",&r,&g,&b,&n);
  for(int i = 0;i <= n / r;i++){
    for(int j = 0;j <= n / g;j++){
      int k = n - i * r - j * g;
      if(k > -1 && k % b < 1){
        cnt++;
      }
    }
  }
  printf("%d\n",cnt);
  return 0;
}

Measured memory_bytes: 128