akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
//#define int long long //Strong Power
#ifdef LOCAL
#define lout cout
#else
//stringstream devnull;
ostream devnull(0);
#define lout devnull
#endif
#define AMULET \
  cin.tie(0);  \
  ios::sync_with_stdio(false);
// https://github.com/kurokoji/.cpp-Template/blob/master/template/template2.cpp
#define GET_MACRO(_1, _2, _3, _4, NAME, ...) NAME
#define rep(...)                                 \
  GET_MACRO(__VA_ARGS__, rep4, rep3, rep2, rep1) \
  (__VA_ARGS__)
#define rep1(n) rep2(_, n)
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, n) rep4(i, a, n, 1)
#define rep4(i, a, n, d) for (decltype(n) i = (a); i < (n); i += (d))
#define rrep(...)                                    \
  GET_MACRO(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1) \
  (__VA_ARGS__)
#define rrep1(a) rrep2(_, a)
#define rrep2(i, a) rrep3(i, a, 0)
#define rrep3(i, a, n) rrep4(i, a, n, 1)
#define rrep4(i, a, n, d) for (decltype(a) i = (a); i >= (n); i -= (d))
// -----
typedef long long ll;
typedef long long lint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;
template <class C>
inline void vcin(C &c);
template <class C, class D>
inline void vcin(C &c, D &d);
template <class C>
inline void vcout(const C &c, const string separate = "\n");
template <class T = int>
inline T in();

void solve()
{
  while (true)
  {
    auto b = in<lint>();
    if (b == 0)
    {
      break;
    }
    lint gn;
    lint u, d;
    rrep(n, (lint)sqrt(2 * b), 1)
    {
      lout << "n:" << n << endl;
      u = 2 * b - n * n + n;
      d = 2 * n;

      lout << "ud:" << u << " " << d << endl;
      if (u <= 0)
      {
        continue;
      }
      if (u % d == 0)
      {
        gn = n;
        break;
      }
    }
    cout << u / d << " " << gn << endl;
  }
}

signed main()
{
  AMULET
  solve();
  return 0;
}

template <class C>
inline void vcin(C &c)
{
  for (auto &a : c)
  {
    cin >> a;
  }
}
template <class C, class D>
inline void vcin(C &c, D &d)
{
  for (auto it1 = c.begin(), it2 = d.begin(); it1 != c.end() && it2 != d.end(); it1++, it2++)
  {
    cin >> *it1 >> *it2;
  }
}
template <class C>
inline void vcout(const C &c, const string separate)
{
  for (auto it = c.begin(); it != c.end(); it++)
  {
    if (it != c.begin())
      cout << separate;
    cout << *it;
  }
}
template <class T = int>
inline T in()
{
  T x;
  cin >> x;
  return (x);
}



Measured memory_bytes: 3136
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <map>
#include <string>
#include <iostream>
#define LL long long
using namespace std;
const LL Mod = 998244353;
map <string, LL> mp;
string s;
LL F(string st) {
	if(!st.size()) return 1;
	if(mp.count(st)) return mp[st];
	LL res = F(st.substr(1));
	if(st[0] == '1') res = res*2%Mod;
	LL sz = st.size();
	for(LL i = 1; i <= sz; i++){
		string tmp = "";
		for(LL j = 1; j <= i; j++) tmp += '1';
		for(LL j = 0; j+i <= sz; j += i){
			for(LL k = 0; k < i; k++) if(st[j+k] == '0') tmp[k] = '0';
			if(j) res = (res+F(tmp)*F(st.substr(j+i)))%Mod;
		}
	}
	return mp[st] = res;
}
int main() {
	LL i, j, k;
	cin >> s;
	cout << F(s) << endl;
	return 0;
}

Measured memory_bytes: 5632
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int a[200010],b[200010],n,c[200010];
int num[30];
int get1(int k)
{
	int l=1,r=n,ans=n+1;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(c[mid]>=k) ans=mid,r=mid-1;
		else l=mid+1;
	}
	return ans;
}
int get2(int k)
{
	int l=1,r=n,ans=0;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(c[mid]<k) ans=mid,l=mid+1;
		else r=mid-1;
	}
	return ans;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	int T=1;
	for(int I=0;I<29;I++)
	{
		int t=(1<<(I+1))-1;
		for(int i=1;i<=n;i++) c[i]=b[i]&t;
		sort(c+1,c+n+1);
		for(int i=1;i<=n;i++)
		{
			int x=a[i]&t;
			int l=get1(T-x),r=get2(2*T-x);
			if(l<=r) num[I]+=(r-l+1);
			l=get1(3*T-x);r=get2(4*T-x);
			if(l<=r) num[I]+=(r-l+1);
		}
		T<<=1;
	}
	int ans=0;
	for(int i=0;i<29;i++) if(num[i]&1) ans+=(1<<i);
	printf("%d",ans);
}

Measured memory_bytes: 2560
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep2(i, n) for(int i = 1; i <= (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize("Ofast")
using namespace std;
typedef int64_t ll;
typedef long double ld;
const ll INF=(1LL<<60);
const ld pi=acosl(1);
const ll mod = 1000000007;
//const ll mod = 998244353;
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const int ddx[8]={1,0,-1,-1,-1,0,1,1};
const int ddy[8]={1,1,1,0,-1,-1,-1,0};

void solve(){
  vector<ll>v;
  string s;cin>>s;
  ll n=s.size();
  rep(i,n)if(s[i]=='R'&&s[i+1]=='L')v.push_back(i);

  //for(auto&&i:v)cout<<i<<" ";
  vector<ll>ans(n,0);
  rep(i,n){
    if(s[i]=='R'){
      ll index=*lower_bound(all(v),i);
      ans[index+abs(i-index)%2]++;
    }
    if(s[i]=='L'){
      ll index=*(lower_bound(all(v),i)-1);
      ans[index+abs(i-index)%2]++;
    }
  }

  for(auto&&i:ans)cout<<i<<" ";cout<<endl;
}

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);cout<<fixed;
  cout<<setprecision(30);
  solve();
}


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

#pragma GCC optimize "trapv"
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define rep(i,a,b) for(int i=a; i<b; i++)
#define drep(i,a,b) for(int i=a; i>b; i--)
#define vi vector<int>
#define pii pair<int,int>
#define pb push_back
#define ll long long
#define inf 1e+18L
#define mod 1000000007

const auto pi = 3.14159265358979;

template <typename T>
T numdigits(T n)
{
    return (floor(log10(n)) + 1);
}

template <typename T>
T modpower(T x, T y, T m=mod)
{
    T res = 1;
    x %= m;
    if(x == 0) return 0;
    while(y > 0)
    {
        if(y&1) res = (res*x)%m;
        y >>= 1;
        x = (x*x)%m;
    }
    return res;
}

void solve()
{
    //code
    int n, m;
    cin >> n >> m;
    vi a(m);
    rep(i,0,m) cin >> a[i];
    ll sumDays = 0;
    for(auto x : a)
    {
        sumDays += (ll) x;
    }
    if(sumDays > n) cout << "-1\n";
    else cout << (ll) n - sumDays << "\n";
}

int main()
{
    FASTIO
//    int t;
//    cin >> t;
//    while(t--)
        solve();
    return 0;
}

Measured memory_bytes: 3692
#include <bits/stdc++.h>
using namespace std;
#define popcnt(a) __builtin_popcount(a)

#define error(args...)                       \
{                                            \
    cerr<<"LINE "<<__LINE__;                 \
    string _s = #args;                       \
    replace(_s.begin(), _s.end(), ',', ' '); \
    stringstream _ss(_s);                    \
    istream_iterator<string> _it(_ss);       \
    err(_it, args);                          \
    cerr<<endl;                              \
}
void err(istream_iterator<string> it)
{
} 
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args)
{
  cerr<<' '<< *it << " = " << a ;
  err(++it, args...);
} 
typedef long long ll;
const int N = 1e5+1 , M = 5e5+1, OO = 0x3f3f3f3f,MOD = 1e9+7;
int arr[100];
int main()
{
  int n;
  scanf("%d",&n);
  int sum=0;
  for(int i=0;i<n;++i) scanf("%d",arr+i),sum+=arr[i];
  
  int p = sum/n;
  int ans=0,ans1=0;
  for(int i=0;i<n;++i)
  {
    ans+= (arr[i]-p)*(arr[i]-p);
    ans1+=(arr[i]-(p+1))*(arr[i]-(p+1));
  }

  printf("%d\n",min(ans,ans1));
  #ifdef _LOCAL_DEFINE  
  cerr << (double)clock() * 1.0 / CLOCKS_PER_SEC << endl;
  #endif
  return 0; 
}

Measured memory_bytes: 256
n1,n2,n3=map(int, input().split())
n4,n5,n6=map(int, input().split())
n7,n8,n9=map(int, input().split())
M=[n1,n2,n3,n4,n5,n6,n7,n8,n9]
O=[0,0,0,0,0,0,0,0,0]
N=int(input())
for i in range(N):
 a=int(input())
 if a in M:
  b=M.index(a)
  if O[b]==0:
   O[b]+=1
a1=[1,0,0,1,0,0,1,0,0]
a2=[0,1,0,0,1,0,0,1,0]
a3=[0,0,1,0,0,1,0,0,1]
a4=[1,1,1,0,0,0,0,0,0]
a5=[0,0,0,1,1,1,0,0,0]
a6=[0,0,0,0,0,0,1,1,1]
a7=[1,0,0,0,1,0,0,0,1]
a8=[0,0,1,0,1,0,1,0,0]
a=[a1,a2,a3,a4,a5,a6,a7,a8]
d=0
for i in range(8):
 c=0
 for j in range(9):
  c+=a[i][j]*O[j]
 if c==3:
  d+=1
if d>=1:
 print("Yes")
else:
 print("No")

Measured memory_bytes: 3188
#include <stdio.h>

int binarysearch(int*,int,int);

int main(){
  int ns,nt,i=0,x,count=0;

  scanf("%d",&ns);
  
  int s[ns];
  while(i<ns){
    scanf("%d",&s[i]);
    i++;
  }
  i=0;

  scanf("%d",&nt);

  int t[nt];

  while(i<nt){
    scanf("%d",&t[i]);
    i++;
  }

  i=0;

  for(i=0;i<nt;i++){
    x=binarysearch(s,t[i],ns);
    if(x>=0){
      if(s[x]==t[i]) count++;
    }
  }
  
  printf("%d\n",count);
  return 0;
}
  
int binarysearch(int *s, int t,int ns){
  int not=-1,left=0,right=ns,mid;

  while(left<right){
    mid=(left+right)/2;
    if(s[mid]==t) return mid;

    else if(t<s[mid]) right=mid;

    else left=mid+1;
  }

  return not;
  
}



Measured memory_bytes: 2268
#include <stdio.h>
#include <iostream>

using namespace std;
int main()
{
  string s;
  cin >> s;
  int counter = 0;
  if (s[0] == '1')
    ++counter;
  if (s[1] == '1')
    ++counter;
  if (s[2] == '1')
    ++counter;
  cout << counter << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

int n, d, x;
int a[105], sum, i , j, m;

int main()
{
	while(cin >> n)
	{
		cin >> d >> x;
		for(i = 0; i < n; i++)
			cin >> a[i];
		sum = n;
		for(i = 0; i < n; i++)
		{
			for(j = 1; ; j++)
			{
				m = (j * a[i] + 1);
				if(m <= d) sum++;
				else break;
			}
		}
		cout << sum + x << endl;
	}
	return 0;
}

Measured memory_bytes: 256
from sys import stdout
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = inl()
acc = [0]*(n+1)
for i in range(n):
    acc[i+1] = acc[i]+a[i]
h = acc[n]/2
j = -1
for i in range(n):
    if acc[i]<=h and h<acc[i+1]:
        j = i
        break
ddprint(acc)
ddprint(j)
if acc[j]==h:
    print(0)
    exit()
x = min(h-acc[j], acc[j+1]-h)
print(int(2*x))


Measured memory_bytes: 89296
#!/usr/bin/env python3
n, m = input().split()
a = set()
b = set()
for _ in range(int(m)):
    r = set(input().split())
    if "1" in r:
        a |= r
    if n in r:
        b |= r
print("POSSIBLE" if len(a & b) > 0 else "IMPOSSIBLE")


Measured memory_bytes: 29792
process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data', function (chunk)
{
  var x = chunk.split(" ");
  a = parseFloat(x[0]);
  b = parseFloat(x[1]);
  c = parseFloat(x[2]);
  
  c_rad = c / 180 * Math.PI
  s = 0.5 * a * b * Math.sin(c_rad);
  l = a + b + Math.sqrt(a * a + b * b - 2 * a * b * Math.cos(c_rad));
  h = s / a * 2;

  console.log(s);
  console.log(l);
  console.log(h);
});

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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


#define PI 3.14159265358979323846


int main() {
    i64 A, B, H, M; cin >> A >> B >> H >> M;
    f64 thA = (H * 60 + M) * 2 * PI / (f64)(12 * 60);
    f64 thB = M * 2 * PI / 60.0;
    f64 ax = A * cos(thA);
    f64 ay = A * sin(thA);
    f64 bx = B * cos(thB);
    f64 by = B * sin(thB);
    f64 d = sqrtl((ax - bx) * (ax - bx) + (ay - by) * (ay - by));
    cout << setprecision(10) << d << endl;

    return 0;
}

Measured memory_bytes: 4144
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string str;
  
  cin >> str;
  
  if((str.at(2)==str.at(3)) && (str.at(4)==str.at(5))){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

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

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

  for (char c: S) {
    if (c == '1') {
      cout << '9';
    } else if (c == '9') {
      cout << '1';
    } else {
      cout << c;
    }
  }
  cout << endl;
}


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

using ll = long long;
#define ALL(c) (c).begin(), (c).end()
const int MOD = 1000000007;

int main() {
    int n, h, w;
    cin >> n >> h >> w;
    int a, b;
    int t = 0;
    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        if (a >= h && b >= w) {
            t++;
        }
    }
    cout << t << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define maxn (100001)

vector<int> cnt(maxn);
int main() {
  int n; cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    cnt[a[i]]++;
    if (a[i] < maxn-1) cnt[a[i]+1]++;
    if (a[i] > 0) cnt[a[i]-1]++;
  }
  int answer = *max_element(cnt.begin(), cnt.end());
  cout << answer << endl;
  return 0; 
}

Measured memory_bytes: 1024
#include <iostream>

using namespace std;

int main(){
  int N, max, a, tmp;
  long long sum = 0;
  cin >> N;
  cin >> max;
  for(int i = 0; i < N - 1; i++){
    cin >> a;
    tmp = max - a;
    if(0 > tmp){
      max = a;
    }
    else{
      sum += tmp;
    }
  }        
  cout << sum << endl;
  return 0;
}

Measured memory_bytes: 3628
from itertools import accumulate
from operator import add


h, w, k = map(int, input().split())

white_count = [0] * (w+1)
prev = [0] * (w+1)
for _ in range(h):
    line = iter('0'+input())
    cumsum_1d = accumulate(map(int, line))
    cumsum_2d = list(map(add, prev, cumsum_1d))
    prev = cumsum_2d
    white_count += cumsum_2d


def get_white(sy, sx, ny, nx):
    a = sy*(w+1) + sx
    b = sy*(w+1) + nx
    c = ny*(w+1) + sx
    d = ny*(w+1) + nx
    return white_count[d] - white_count[c] - white_count[b] + white_count[a]


ans = []
for pattern in range(2**(h-1)):
    dived = [0] + [y+1 for y in range(h-1) if (pattern>>y) & 1] + [h]
    slash_count = len(dived) - 2

    prev_x = 0
    for div_x in range(1, w + 1):
        white_include = 0
        for idx in range(len(dived)-1):
            prev_y = dived[idx]
            div_y = dived[idx+1]
            white = get_white(prev_y, prev_x, div_y, div_x)
            if white > white_include:
                white_include = white

        if white_include > k:
            slash_count += 1
            if prev_x == div_x - 1:
                break
            prev_x = div_x - 1

    else:
        ans.append(slash_count)

print(min(ans))


Measured memory_bytes: 43612
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <unordered_map>

using namespace std;
using ll = long long;

void _cin(){} template <class Head, class... Tail> void _cin(Head&& head, Tail&&... tail){ cin >> head; _cin(forward<Tail>(tail)...); }
void _cout(){ cout << "\n"; } template <class Head, class... Tail> void _cout(Head&& head, Tail&&... tail){ cout << head; _cout(forward<Tail>(tail)...); }
int gcd(int a, int b){ return (b == 0) ? a : gcd(b, a % b); }
template<typename S, typename T> ostream& operator<<(ostream &os, const pair<S, T> &p){ cout << "[" << p.first << ", " << p.second << "]"; return os; }

#define Sq(x) (x)*(x)
#define For(i, n) for(int i = 0; i < (n); i ++)
#define Rep(n) For(_, n)
#define Range(c) c.begin(), c.end()
#define RevRange(c) c.rbegin(), c.rend()
#define Contains(c, x) (find(Range(c), x) != c.end())
#define Search(rb, re, x) distance(rb, find(rb, re, x))
#define Sort(a) sort(Range(a))
#define DeSort(a) sort(RevRange(a))
#define Reverse(c) reverse(Range(c))
#define Unique(a) a.erase(unique(Range(a)), a.end())
#define Cusum(T, xs, sxs) vector<T> sxs(xs.size()+1); For(i, (int)xs.size()) sxs[i+1] = sxs[i] + xs[i]
#define Cin(T, ...) T __VA_ARGS__; _cin(__VA_ARGS__)
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i]
#define Cins2(T, n, xs, ys) vector<T> xs(n), ys(n); For(i, n) cin >> xs[i] >> ys[i]
#define Cins3(T, n, xs, ys, zs) vector<T> xs(n), ys(n), zs(n); For(i, n) cin >> xs[i] >> ys[i] >> zs[i]
#define Cinss(T, n, m, xs) Vec2(T, n, m, xs); For(i, n) For(j, m) cin >> xs[i][j]
#define Cinm(T, n, map) unordered_map<T, int> map; Rep(n){ Cin(T, x); map[x] ++; }
#define Cout(...) _cout(__VA_ARGS__)
#define Couts(xs) { for(const auto &e : xs) cout << e << " "; cout << "\n"; }
#define Coutyn(cond) Cout((cond) ? "yes" : "no")
#define CoutYn(cond) Cout((cond) ? "Yes" : "No")
#define CoutYN(cond) Cout((cond) ? "YES" : "NO")
#define Return(expr) { Cout(expr); return 0; }
#define vc vector
#define Mini(a, x) a = min(a, x)
#define Maxi(a, x) a = max(a, x)

// constexpr int MOD = 1e9+7;

int main(void){
    Cin(ll, n, a, b);
    Cout( a*(n/(a+b)) + min(n%(a+b), a) );
    
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vector <ll> vec
#define pair <ll,ll> pa
#define make_pair mp
#define push_back pb
int main()
{	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll n,arr[200234],freq[200234];
	cin>>n;
	ll i;
	memset(freq,0,sizeof(freq));
	for(i=0;i<n;i++)
		{
			cin>>arr[i];
			freq[arr[i]]++;
		}
	ll count=0;
	for(i=0;i<=n;i++)
	{	ll n=freq[i];
		count+=(n*(n-1))/2;
	}
	ll copy=count;
	for(i=0;i<n;i++)
	{	count=copy;
		ll n=freq[arr[i]];
		count-=(n*(n-1))/2;
		n--;
		count+=(n*(n-1))/2;
		cout<<count<<endl;
	}

	return 0;
}

Measured memory_bytes: 5760
n=int(input())
a=list(map(int,input().split()))
a.insert(0,0)
a.insert(n+1,0)
b=[0]*(n+1)

for i in range(n+1):
    b[i]=abs(a[i]-a[i+1])
ans=sum(b)
#print(a,b)
for i in range(n):
    #print(ans,b[i],b[i+1],abs(a[i]-a[i+2]))
    print(ans-b[i]-b[i+1]+abs(a[i]-a[i+2]))



Measured memory_bytes: 14048
Scanf.scanf "%d" (fun n ->
    let ab = Array.init n (fun _ -> Scanf.scanf " %d %d" (fun a b -> a, b)) in

    let rec loop i acc =
        if i < 0 then acc else
            let a, b = ab.(i) in
            let c = (a + acc + b - 1) / b * b - a - acc in
            loop (i - 1) (acc + c)
    in
    loop (n - 1) 0 |> Printf.printf "%d\n"
)

Measured memory_bytes: 9320
#include <bits/stdc++.h>
       
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
class ModInt {
  static int MOD;
  long long x;

 public:
  static void mod(int m) { MOD = m; }

  ModInt(long long v = 0) : x(v % MOD) {
    if (x < 0) x += MOD;
  }

  ModInt& operator+=(const ModInt& r) {
    x += r.x;
    if (x >= MOD) x -= MOD;
    return *this;
  }

  ModInt& operator-=(const ModInt& r) {
    x -= r.x;
    if (x < 0) x += MOD;
    return *this;
  }
  ModInt& operator*=(const ModInt& r) {
    x = (x * r.x) % MOD;
    return *this;
  }
  ModInt& operator/=(const ModInt& r) {
    *this *= r.inverse();
    return *this;
  }

  ModInt operator-() const { return ModInt(-x); }

  ModInt operator+(const ModInt& r) const { return ModInt(*this) += r; }
  ModInt operator-(const ModInt& r) const { return ModInt(*this) -= r; }
  ModInt operator*(const ModInt& r) const { return ModInt(*this) *= r; }
  ModInt operator/(const ModInt& r) const { return ModInt(*this) /= r; }
  bool operator==(const ModInt& r) const { return x == r.x; }
  bool operator!=(const ModInt& r) const { return x != r.x; }

  ModInt inverse() const {
    long long a = x, b = MOD, u = 1, v = 0, t;
    while (b > 0) {
      t = a / b;
      swap(a -= t * b, b);
      swap(u -= t * v, v);
    }
    return ModInt(u);
  }

  ModInt pow(long long n) const {
    ModInt ret(1), mul(x);
    while (n > 0) {
      if (n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }

  friend ostream& operator<<(ostream& os, const ModInt& x) { return os << x.x; }

  friend istream& operator>>(istream& is, ModInt& x) { return is >> x.x; }

  int getMod() { return MOD; }

  long long val() { return x; }
};
int ModInt::MOD = 1000000007;

int main() {
  int N;
  cin >> N;
  vector<int> C(N, 0);

  for (int i = 0; i < (int)(N); ++i) {
    int A;
    cin >> A;
    C[A] += 1;
  }

  auto ans = [&]() -> ll {
    ModInt res = 1;
    if (N % 2 == 0) {
      for (int i = 0; i < (int)(N); ++i) {
        if (i % 2 == 0) {
          if (C[i] != 0) return 0;
        } else {
          if (C[i] != 2) return 0;
          res *= C[i];
        }
      }
    } else {
      for (int i = 0; i < (int)(N); ++i) {
        if (i % 2 == 0) {
          if (i == 0 && C[i] != 1) return 0;
          if (i != 0 && C[i] != 2) return 0;
          res *= C[i];
        } else {
          if (C[i] != 0) return 0;
        }
      }
    }
    return res.val();
  };

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


Measured memory_bytes: 640
n = int(input())

blist = list(map(int, input().split()))

cnt = 0

for i in range(n):
    minj = i
    for j in range(i, n):
        if blist[j] < blist[minj]:
            minj = j
    if i != minj:
        cnt += 1
        blist[i], blist[minj] = blist[minj], blist[i]

for i in range(n):
    if i == n-1:
        print(blist[i])
    else:
        print(str(blist[i]) + " ", end="")

print(cnt)



Measured memory_bytes: 5612
#include <iostream>
#include <vector>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#define myfor(i,N) for(i=0;i<N;i++)
#define myforFL(i,f,l) for(i=f;i<l;i++)
#define myforInv(i,N) for(i=N;i>=0;i--)
#define myforFLInv(i,f,l) for(i=f;i>l;i--)

using namespace std;

int main(){
	long N,A[80],money=1000,stock=0;
	long dif[79];
	cin >> N;
	int i;
	myfor(i,N){
		cin >> A[i];
		if(i>0)dif[i-1] = A[i] - A[i-1];
	}

	long buyPrice=300,cellPrice=0;
	myfor(i,N){
		if(dif[i] > 0 && buyPrice > A[i]){
			if(cellPrice != 0){
				money += stock *cellPrice;
				stock = 0;
				cellPrice = 0;
			}
			buyPrice = A[i];
		}
		if(dif[i] < 0 && cellPrice < A[i]){
			if(buyPrice !=300){
				stock = money/buyPrice;
				money%=buyPrice;
				buyPrice = 300;
			}
			cellPrice = A[i];
		}
	}
	if(buyPrice !=300){
		stock = money/buyPrice;
		money%=buyPrice;
		buyPrice = 300;
	}
	if(cellPrice != 0){
		money += stock *cellPrice;
		stock = 0;
		cellPrice = 0;
	}
	money += stock *A[N-1];

	cout << money << endl;

	return 0; 

}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
using pll = pair<ll, ll>;


int main(){
    ll n, d;
    cin >> n >> d;
    vector<ll> a(n);
    for(auto& i : a) cin >> i;
    auto cost = [&](ll x, ll y){
        return a[x] + a[y] + abs(x - y) * d;
    };
    vector<ll> l(n), r(n);
    l[0] = 0;
    for(ll i = 1; i < n; i++) l[i] = min(l[i - 1], i, [&](ll x, ll y){ return cost(i, x) < cost(i, y); });
    r[n - 1] = n - 1;
    for(ll i = n - 1; i--; ) r[i] = min(r[i + 1], i, [&](ll x, ll y){ return cost(i, x) < cost(i, y); });
    ll ans = 0;
    pll last;
    for(ll i = 0; i < n - 1; i++) if(last != pll{l[i], r[i + 1]}){
        last = {l[i], r[i + 1]};
        ans += cost(l[i], r[i + 1]);
    }
    for(ll i = 1; i < n - 1; i++) if(l[i] != i && r[i] != i) ans += min(cost(i, l[i - 1]), cost(i, r[i + 1]));
    cout << ans << endl;
}


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

int main() {
  int N, K;
  cin >> N >> K;
  
  vector<int> fru(N);
  for (int i = 0; i < N; i++) {
    cin >> fru.at(i);
  }
  
  sort(fru.begin(), fru.end());
  
  int j = 0;
  int b = 0;
  while (j < K) {
    b += fru.at(j);
    j++;
  }
  
  cout << b <<endl;
}

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

int main(void){
	long long A;
	double B;
	cin >> A >> B;
	int B100 = 100*B + 0.1;
	long long result = A*B100;
	result /= 100;
	cout << result << endl;
return 0;
}



Measured memory_bytes: 3160
t = list(input())

if len(t) == 1 and t[0] == "?":
    t[0] = "D"
    print(t[0])
    exit()

if t[0] == "?":
    if t[1] == "P":
        t[0] = "D"
    else:
        t[0] = "P"
for i in range(1, len(t)-1):
    if t[i] == "?" and t[i-1] == "P":
        t[i] = "D"
    elif t[i] == "?" and t[i+1] == "D":
        t[i] = "P"
    elif t[i] == "?" and t[i+1] == "?":
        t[i] = "P"
        t[i+1] = "D"
    elif t[i] == "?":
        t[i] = "D"
if len(t) > 1:
    if t[-1] == "?":
        t[-1] = "D"

print("".join(t))

Measured memory_bytes: 73740
def ACWA(p,j,p_list):
    if j=="AC":
        p_list[p][0]=1
    else:
        p_list[p][1]+=1
    return p_list
    
N,M = map(int,input().split(" "))
p_list = {}
wa_count = 0

for _ in range(M):
    In = input().split()
    if (In[0] in p_list) == False:
        p_list[In[0]]=[0,0]
        p_list = ACWA(In[0],In[1],p_list)
    else:
        if p_list[In[0]][0]==1:
            continue
        else:
            p_list = ACWA(In[0],In[1],p_list)
                
List = list(p_list.values())
a = 0
b = 0

for i in range(len(List)):
    if List[i][0]==1:
        a+=List[i][0]
        b+=List[i][1]

print("{} {}".format(a,b))

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

#define rep(i,n) for (int i = 0; i< (n); ++i)
#define vvec(m,n) vector<vector<int>> (int(m), vector<int>(n))
#define ALL(a) (a).begin(), (a).end()

using ll = long long;

int main(){
    int A, B;
    cin >> A >> B;
    bool res = true;
    if(A*B % 2 == 0) res = false;
    string ans;
    if(res){
        ans = "Yes";
    }else{
        ans = "No";
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    long  A, B, N;
    cin >> A >> B >>N;
    long ans_x = B * (long)((N+1) / B) - 1;
    if (ans_x == -1) {
        ans_x = N;
    }
    cout << (floor(((double)A/(double)B)* ans_x) - A * floor(ans_x/(double)B)) << endl;
}


Measured memory_bytes: 3736
// 2013/05/13 Tazoe

#include <iostream>
using namespace std;

int main()
{
	int L, A, B, C, D;
	cin >> L;
	cin >> A;
	cin >> B;
	cin >> C;
	cin >> D;

	int E = (A-1)/C+1;
	int F = (B-1)/D+1;

	if(E>F){
		cout << L-E << '\n';
	}
	else{
		cout << L-F << '\n';
	}

	return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>

using namespace std;

int x,y;
int sx,sy;
int N;
int hx[24],hy[24];
int fie[12][12];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
map<int,int> memo[24];

int dfs(int pos,int bit,bool done[12][12],int home){
	if(memo[pos].find(bit)!=memo[pos].end())return memo[pos][bit];
	if(bit==(1<<N)-1){
		for(int i=0;i<4;i++){
			int cx=hx[pos]+dx[i],cy=hy[pos]+dy[i];
			while(fie[cx][cy]!=-1){
				if(fie[cx][cy]==100)return 1;
				cx+=dx[i],cy+=dy[i];
			}
		}
		return 0;
	}
	int ans=0;
	for(int i=0;i<4;i++){
		int cx=hx[pos]+dx[i],cy=hy[pos]+dy[i];
		while(fie[cx][cy]==-2 || fie[cx][cy]==100 || done[cx][cy]==true){
			cx+=dx[i],cy+=dy[i];
		}
		if(fie[cx][cy]!=-1){
			done[cx][cy]=true;
			ans+=dfs(fie[cx][cy] , bit | (1<<fie[cx][cy]), done,home+1);
			done[cx][cy]=false;
		}
	}
	if(home<15)memo[pos][bit]=ans;
	return ans;
}

int main(void){
	while(1){
		scanf("%d%d",&x,&y);
		if(x==0 && y==0)break;
		N=0;
		for(int i=0;i<24;i++){
			memo[i].clear();
		}
		for(int i=0;i<12;i++){
			for(int j=0;j<12;j++){
				fie[j][i]=-1;
			}
		}
		for(int i=1;i<=y;i++){
			for(int j=1;j<=x;j++){
				scanf("%d",&fie[j][i]);
				if(fie[j][i]==0){
					fie[j][i]=-2;
				}
				if(fie[j][i]==2){
					fie[j][i]=100;
					sx=j;
					sy=i;
				}
				if(fie[j][i]==1){
					fie[j][i]=N;
					hx[N]=j;
					hy[N]=i;
					N++;
				}
			}
		}
		hx[N]=sx,hy[N]=sy;
		bool done[12][12];
		memset(done,false,sizeof(done));
		cout << dfs(N,0,done,0) << endl;
	}
    return 0;
}

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

#define rep(i,beg,end)   for (auto i=(beg);i<(end);i++)
#define all(cont)           begin(cont), end(cont)
#define rall(cont)           rbegin(cont), rend(cont)
using ll = long long;
using vi = vector<ll>;
const ll INFMAX = LLONG_MAX;
const ll INFMIN = LLONG_MIN;
const ll MOD = 1000000007;

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n;
	cin >> n;
	vi a(n), b(n), c(n - 1);
	rep(i, 0, n) cin >> a[i];
	rep(i, 0, n) cin >> b[i];
	rep(i, 0, n-1) cin >> c[i];
	ll happy = accumulate(all(b), 0LL);
	rep(i, 0, n - 1) {
		if (a[i] + 1 == a[i + 1])
			happy += c[a[i]-1];
	}
	cout << happy << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define SELECTER(_1, _2, _3, SELECT, ...) SELECT
#define REP1(i, n) for(int (i)=0; (i)<(n); (i)++)
#define REP2(i, a, b) for(int (i)=(a); (i)<(b); (i)++)
#define REP(...) SELECTER(__VA_ARGS__, REP2, REP1,) (__VA_ARGS__)
#define MOD 1000000007

template <class T> ostream& operator<<(ostream& os, const vector<T>& v){ os << "{"; for(size_t i=0; i<v.size(); i++) os << v[i] << (i+1==v.size() ? "" : ", "); os << "}"; return os; }
template <class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p){ return os << "{" << p.first << ", " << p.second << "}"; }

int main(){
    int N;
    string S;
    cin >> N >> S;
    char cur = '.';
    int ans = 0;
    REP(i, N){
        if(S[i] != cur){
            ans++;
            cur = S[i];
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 512
N, K = map(int, input().split())
if K == 0:
    print(N * N)
    exit()
ans = 0
for b in range(K + 1, N + 1):
    p = N // b
    ans += p * (b - K) + max(0, N - p * b - K + 1)
print(ans)

Measured memory_bytes: 39280
from collections import deque


def solve():
    h, w = map(int, input().split())
    a = [input() for _ in range(h)]

    q = deque()

    arrived = [[True] * (w + 2)] + \
              [[True] + [False] * w + [True] for _ in range(h)] + \
              [[True] * (w + 2)]

    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                q.append([i+1, j+1])
                arrived[i+1][j+1] = True

    ans = 0
    while q:
        ans += 1
        pop_max = len(q)
        cnt = 0
        while cnt != pop_max:
            i, j = q.popleft()
            if not arrived[i-1][j]:
                arrived[i-1][j] = True
                q.append([i-1, j])

            if not arrived[i+1][j]:
                arrived[i+1][j] = True
                q.append([i+1, j])

            if not arrived[i][j-1]:
                arrived[i][j-1] = True
                q.append([i, j-1])

            if not arrived[i][j+1]:
                arrived[i][j+1] = True
                q.append([i, j+1])

            cnt += 1

    ans -= 1
    print(ans)


def main():
    solve()


if __name__ == "__main__":
    main()


Measured memory_bytes: 142172
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	scanInit()
	//combinitMODD()

	n := nextInt()
	p := nextInt() // 0=even, 1=odd
	a := make([]int, n)

	oddnum := 0
	for i := 0; i < n; i++ {
		a[i] = nextInt()
		if a[i]%2 == 1 {
			oddnum++
		}
	}
	evennum := n - oddnum
	cnt := 0

	eway := 1 << evennum
	osum := 0
	if oddnum != 0 {
		osum = 1 << (oddnum - 1)
	}

	cnt = eway * osum
	if oddnum == 0 {
		if p == 0 {
			fmt.Println(1 << n)
		} else {
			fmt.Println(cnt)
		}
	} else {
		fmt.Println(cnt)
	}
}

const modd int = 1000000007
const combMax int = 510000 // combinit用
var combfac [combMax]int   // combinit用
var combfinv [combMax]int  // combinit用
var combinv [combMax]int   // combinit用
func combinitMODD() {
	combfac[0] = 1
	combfac[1] = 1
	combfinv[0] = 1
	combfinv[1] = 1
	combinv[1] = 1
	for i := 2; i < combMax; i++ {
		combfac[i] = combfac[i-1] * i % modd
		combinv[i] = modd - combinv[modd%i]*(modd/i)%modd
		combfinv[i] = combfinv[i-1] * combinv[i] % modd
	}
}

// 1<=k<=n<=10**7
func combinationMODD(n int, k int) int {
	if n < k {
		return 0
	}
	if n < 0 || k < 0 {
		return 0
	}
	return combfac[n] * (combfinv[k] * combfinv[n-k] % modd) % modd
}
func pow(a, b int) int {
	var ret int = 1
	for b > 0 {
		if (b & 1) == 1 {
			ret *= a
		}
		a *= a
		b >>= 1
	}
	return ret
}

// ---- readfunc
var sc = bufio.NewScanner(os.Stdin)

func scanInit() {
	const cap = 200 * 1024 // default=64*1024
	var buf = make([]byte, cap)
	sc.Buffer(buf, cap)
	sc.Split(bufio.ScanWords)
	return
}
func nextInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}
func nextStr() string {
	sc.Scan()
	return sc.Text()
}


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

using namespace std;
typedef long long ll;
ll n,a[100010],ans;
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int i=1,pr=0;i<=n;i++)
	{
		if(!a[i]){pr=0; continue;}
		if(pr){ans++; a[i]--;}
		ans+=(a[i]/2); pr=a[i]&1;
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<int,int> P;
#define Mod 1000000007


int main(){
    int i,j;
    int n;
    string s;
    
	cin>>n;
	cin>>s;
    int r[324000];

	for(i=0;i<n;i++){
		if(s[i]=='E') r[i]=1;
		if(i) r[i]+=r[i-1];
	}
	int ans=1<<20;
	
    for(i=0;i<n;i++){
        int tmp=0;
        if(i) tmp=i-r[i-1];
        tmp+=r[n-1]-r[i];
        ans=min(ans,tmp);
    }
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 1796
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>
#include<complex>

using namespace std;

#define ll long long
#define ld long double
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

const double PI=acos(-1);
const double EPS=1e-9; //うまくいかなかったらゆるめる

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef pair<int,pii> pip;
typedef vector<pii> vp;
typedef vector<vi> vvi;

int gcd(int a, int b){if(b==0) return a;return gcd(b,a%b);}
int lcm(int a, int b){return a/gcd(a,b)*b;}


signed main(void) {
    int n;
    cin >> n;
    double t = n/3.0;
    cout << shosu(10) << t*t*t << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define forn(i,b) for(int i=0 ; i< b ;i++)
#define for1(i,b) for(int i=1 ; i<=b ;i++)
#define reps(i,a,b) for(int i=a ; i< b.length() ;i++)
typedef long long ll;
#define MOD 1000000007



using namespace std;

int main()
{
  long long H,res=0;
  int N,x;

  cin>>H>>N;
  for(int i=0;i<N ; i++){
    cin>>x;
    res+=x;
  }
  if(res>=H)cout<<"Yes";
  else cout<<"No";


  return 0 ;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=100005;
const ll INF=1LL<<60;

vector<pair<int,ll>> S[MAX];
ll dis[MAX][2],pat[MAX][2];
int seen[MAX][2];

void dijkstra(int u,int q){
    dis[u][q]=0;
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> PQ;
    
    PQ.push(make_pair(0,u));
    while(!PQ.empty()){
        ll a=PQ.top().first;
        int b=PQ.top().second;
        PQ.pop();
        if(dis[b][q]<a) continue;
        for(int i=0;i<S[b].size();i++){
            int c=S[b][i].first;
            ll d=S[b][i].second;
            if(dis[c][q]>dis[b][q]+d){
                dis[c][q]=dis[b][q]+d;
                PQ.push(make_pair(dis[c][q],c));
            }
        }
    }
    return;
}//a,dが長さ

void count(int u,int q){
    ll sum=pat[u][q];
    for(int i=0;i<S[u].size();i++){
        int a=S[u][i].first;ll b=S[u][i].second;
        if(dis[u][q]<=dis[a][q]||dis[u][q]!=dis[a][q]+b) continue;
        if(seen[a][q]) sum+=pat[a][q];
        else{
            count(a,q);
            sum+=pat[a][q];
        }
        sum%=mod;
    }
    pat[u][q]=sum;
    seen[u][q]=1;
}

struct edge{
    int s;
    int t;
    ll d;
};

int main(){
    
    int N,M,A,B;cin>>N>>M>>A>>B;
    A--;B--;
    
    vector<edge> G(M*2);
    
    for(int i=0;i<M;i++){
        int s,t;
        ll d;cin>>s>>t>>d;
        s--;t--;
        G[i]={s,t,d};
        G[i+M]={t,s,d};
        S[s].push_back({t,d});
        S[t].push_back({s,d});
    }
    
    ll ans=0;
    
    for(int i=0;i<N;i++){
        dis[i][0]=INF;
        dis[i][1]=INF;
    }
    
    dijkstra(A,0);
    dijkstra(B,1);
    pat[A][0]=1;
    pat[B][1]=1;
    count(B,0);
    count(A,1);
    
    ll maxi=dis[B][0];
    
    if(maxi%2==0){
        for(int i=0;i<N;i++){
            if(dis[i][0]==maxi/2&&dis[i][1]==maxi/2){
                ans+=pat[i][0]*pat[i][1]%mod*pat[i][0]%mod*pat[i][1]%mod;
                ans%=mod;
            }
        }
    }
    
    for(int i=0;i<M*2;i++){
        if(dis[G[i].s][0]+G[i].d==dis[G[i].t][0]&&dis[G[i].t][1]+G[i].d==dis[G[i].s][1]&&dis[G[i].s][0]*2<maxi&&maxi<dis[G[i].t][0]*2&&dis[G[i].t][1]*2<maxi&&maxi<dis[G[i].t][0]*2){
            ans+=pat[G[i].s][0]*pat[G[i].t][1]%mod*pat[G[i].s][0]%mod*pat[G[i].t][1]%mod;
            ans%=mod;
        }
        //cout<<ans<<endl;
    }
    
    cout<<((pat[B][0]*pat[B][0])%mod+mod-ans)%mod<<endl;
}



Measured memory_bytes: 32548
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <set>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <cmath>
#include <math.h>

typedef long long ll;
using namespace std;

int main(void){
    int N;
    cin >> N;
    
    int A[N-1];
    for(int i = 0; i < N-1; i++) cin >> A[i];
    map<int, int> mp;
    for(int i = 0; i <N-1; i++){
        auto itr = mp.find(A[i]);
        if(itr != mp.end()) mp[A[i]] += 1;
        else mp[A[i]] = 1;
    }
    for(int i = 1; i <= N; i++) {
        auto itr = mp.find(i);
        if(itr != mp.end()) cout << mp[i] << endl;
        else cout << 0 << endl;
    }
}



Measured memory_bytes: 13752
/*   _/                _/                 _/_/_/   _/
  _/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/
   _/     _/    _/   _/     _/    _/  _/_/_/     _/
  _/     _/    _/   _/     _/    _/  _/    _/   _/
   _/_/   _/_/       _/_/   _/_/      _/_/     _/ */
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
using ll=long long;
const int MOD=1e9+7;
const double pi=3.14159265358979323846;
const int inf=1e9+5;
const ll INF=1e18+5;
using P=pair<int,int>;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int main() {
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  int n,k,ans=0,a,x[105]={},d;
  cin >> n >> k;
  for(int i=0; i<k; i++) {
    cin >> d;
    for(int j=0; j<d; j++) {
      cin >> a;
      a--;
      x[a]++;
    }
  }
  for(int i=0; i<n; i++) {
    if(!x[i]) {
      ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,x,n) for(int i=x;i<n;i++)
#define mod 1000000007 //10^9+7
#define INF 1000000000000 //10^12
#define F first
#define S second
#define P pair<int,int>
#define all(vec) vec.begin(),vec.end()
//library begin
int gcd(int a,int b){
    if(a%b==0)return b;
    return gcd(b,a%b);
}
int lcm(int a,int b){
    return a*b/gcd(a,b);
}
int log(int a){
    int b=a;
    int cnt=0;
    while(b%2==0){
        b/=2;
        cnt++;
    }
    return cnt;
}
int mypow(int a,int b){
    if(b==0)return 1;
    if(b==1)return a;
    int t=mypow(a,b/2);
    if(b%2==0)return t*t;
    return t*t*a;
}
//Union-Find;
#define MAX_N 200000
int par[MAX_N];
int siz[MAX_N];
int Rank[MAX_N];
void init(int n){
    rep(i,n){
        par[i]=i;
        siz[i]=1;
        Rank[i]=0;
    }
}
int find(int x){
    if(par[x]==x){
        return x;
    }else{
        return par[x]=find(par[x]);
    }
}
void unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)return;
    if(Rank[x]<Rank[y]){
        par[x]=y;
        siz[par[x]]=siz[x]+siz[y];
    }else{
        par[y]=x;
        siz[par[y]]=siz[x]+siz[y];
        if(Rank[x]==Rank[y])Rank[x]++;
    }
}
bool same(int x,int y){
    return find(x)==find(y);
}

//library end
int n;
string s[300000];
map<string,int>mp;
int maxv=0;
vector<string>ans;
signed main(){
    cin>>n;
    rep(i,n){
        cin>>s[i];
        mp[s[i]]++;
    }
    rep(i,n){
        maxv=max(maxv,mp[s[i]]);
    }
    rep(i,n){
        if(mp[s[i]]==maxv){
            ans.push_back(s[i]);
            mp[s[i]]=-1;
        }
    }
    sort(all(ans));
    int l=ans.size();
    rep(i,l)cout<<ans[i]<<endl;
    return 0;
}


Measured memory_bytes: 31088
#include <iostream>
#include <string>

int main()
{
  std::string str;
  std::cin >> str;

  while( ! str.empty() )
  {
    str.pop_back();
    if( str.length() % 2 != 0 ) { continue; }
    if( str.substr(0,str.length()/2) == str.substr(str.length()/2, str.length()/2) )
    {
      break;
    }
  }

  std::cout << str.length();
}

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

#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
// pll pp; -> (pp.first,pp.second)
// vector<vl> pp(n,vl(2)); sort(pp.begin(),pp.end(),[](vl a,vl b){return a[0]<b[0];});

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define RREP(i,n) for(ll (i)=(n)-1;(i)>=0;(i)--)
#define FOR(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
#define FORR(i,a,b) for(ll (i)=(b)-1;(i)>=(a);(i)--)
#define DEBUG(x) cout << #x << ": " << x << endl
#define CHMAX(a,b) a=max((a),(b))
#define CHMIN(a,b) a=min((a),(b))
/*}}}*/
int main() {
  ll A,B,ans;
  cin >> A>>B;
  ans = max(max(A+B,A-B),A*B);
  cout << ans<< endl;
  return 0;
}

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

h_i = input().split()
h_i = [int(N) for N in h_i]
h_i.sort()
if N < K:
    print("0")
else :
    newh_i = h_i[0:N-K]
    print(sum(newh_i))

Measured memory_bytes: 26024
#include <iostream>
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <cctype>
#include <string>

using namespace std;

int main(){ 
  // 入力
  double a, b, C, r;
  cin >> a >> b >> C;
  double S, L, h;
  
  // 前処理
  static const double pi = 3.141592653589793;
  r = 180/C;
  
  // 面積
  S = (a * b * sin(pi/r)) / 2;
 
  // 周囲
  L = a + b + sqrt(a*a+b*b -(2*a*b*cos(pi/r)));

  // 高さ
  h = b * sin(pi/r);

  // 出力
  printf("%lf\n",S);
  printf("%lf\n",L);
  printf("%lf\n",h);

  return 0;
}  


Measured memory_bytes: 3624
#include <stdio.h>
#include <stdlib.h>

int main (void)
{
  int i, j, c1, c2, road, n, m, **map;

  scanf("%d %d", &n, &m);
  map = (int **)malloc(sizeof(int *) * n);
  for (i = 0; i < n; i++) {
    map[i] = (int *)malloc(sizeof(int) * n);
    for (j = 0; j < n; j++) {
      map[i][j] = 0;
    }
  }

  for (i = 0; i < m; i++) {
    scanf("%d %d", &c1, &c2);
    map[c1-1][c2-1]++;
    map[c2-1][c1-1]++;
  }

  for (i = 0; i < n; i++) {
    road = 0;
    for (j = 0; j < n; j++) {
      road += map[i][j];
    }
    printf("%d\n", road);
  }

  for (i = 0; i < n; i++) {
    free(map[i]);
  }
  free(map);

  return 0;
}

Measured memory_bytes: 128
import sys
from collections import defaultdict, deque
import bisect
from heapq import *
from math import factorial, ceil, floor
from collections import defaultdict
import itertools
sys.setrecursionlimit(200000)
input = sys.stdin.readline

# N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
# L = [list(input().strip())  for _ in range(N)]
# S = input().strip()

N, M, = map(int, input().split())

print(ceil(N / M))

Measured memory_bytes: 3700
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author tommy6073
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

class BKagamiMochi {
public:
    void solve(std::istream& in, std::ostream& out) {
        int N;
        in >> N;
        set<int> mochi_set;
        for (int i = 0; i < N; ++i) {
            int d;
            in >> d;
            mochi_set.insert(d);
        }

        out << mochi_set.size();
    }
};


int main() {
	BKagamiMochi solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	N, M := ReadInt(), ReadInt()

	num := make([]int, N)
	red := make([]bool, N)
	for i := 0; i < N; i++ {
		num[i] = 1
		red[i] = false
	}
	red[0] = true

	for i := 0; i < M; i++ {
		x, y := ReadInt()-1, ReadInt()-1
		if num[x] > 0 {
			num[x]--
			num[y]++
			if red[x] {
				red[y] = true
			}
			if num[x] == 0 {
				red[x] = false
			}
		}
	}

	ans := 0
	for i := 0; i < N; i++ {
		if red[i] {
			ans++
		}
	}
	fmt.Println(ans)
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int) { Scan(&i); return }


Measured memory_bytes: 5924
#include<bits/stdc++.h>
using namespace std;
int Cnt[26];
char s[100010];
const int mo=1000000007;
int main(){
	int n;
	scanf("%d",&n);
	scanf("%s",s);
	for (int i=0;i<n;i++){
		Cnt[s[i]-'a']++;
	}
	int Ans=1;
	for (int i=0;i<26;i++){
		Ans=1LL*Ans*(Cnt[i]+1)%mo;
	}
	cout<<(Ans+mo-1)%mo<<"\n";
	return 0;
}

Measured memory_bytes: 384
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] dams = new int[n];
		long[] rains = new long[n];
		for (int i = 0; i < n; i++) {
		    dams[i] = sc.nextInt();
		    if (i % 2 == 0) {
		        rains[0] += dams[i];
		    } else {
		        rains[0] -= dams[i];
		    }
		}
		StringBuilder sb = new StringBuilder();
		sb.append(rains[0]);
		for (int i = 1; i < n; i++) {
		    rains[i] = 2 * dams[i - 1] - rains[i - 1];
		    sb.append(" ").append(rains[i]);
		}
		System.out.println(sb);
   }

}


Measured memory_bytes: 61976