akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
// Runs range sum queries only.
// Sum : O(1)
template <class Abel>
class CumulativeSum
{
	std::vector<Abel> sums_;

public:
	CumulativeSum(const std::vector<Abel> &data) : sums_(data)
	{
		sums_.insert(sums_.begin(), Abel(0));
		for (int i = 1; i < (int)sums_.size(); ++i)
		{
			sums_[i] += sums_[i - 1];
		}
	}

	// Gets the sum of data[0, right)
	Abel Sum(int right) { return sums_[right]; }

	// Gets the sum of data[left, right)
	Abel Sum(int left, int right) { return Sum(right) - Sum(left); }
};
int main()
{
	int n;
	cin >> n;
	string s;
	cin >> s;
	vector<int> white(n), black(n);
	for (int i = 0; i < n; ++i)
	{
		if (s[i] == '.')
		{
			white[i] = 1;
		}
		else
		{
			black[i] = 1;
		}
	}
	reverse(white.begin(), white.end());
	CumulativeSum<int> white_sum(white), black_sum(black);
	int ans = 1e9;
	for (int i = 0; i <= n; ++i)
	{
		ans = min(ans, black_sum.Sum(i) + white_sum.Sum(n - i));
	}
	cout << ans << endl;
}

Measured memory_bytes: 4340
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int a[2][110];

int main()
{
    int n;
    scanf("%d",&n);
    memset(a,0,sizeof(a));
    getchar();
    for(int i=1;i<=n;i++)
    {
        char t;
        scanf("%c",&t);
        //printf("%d\n",t);
        if(a[0][t]=='\0')
            a[0][t]=i;
        else
            a[1][t]=i;
    }
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        int u=0;
        for(int j=0;j<26;j++)
        {
            if(a[0]['a'+j]<i&&a[1]['a'+j]>=i)
                u++;
        }
        if(u>sum)
            sum=u;
    }
    cout<<sum<<endl;
}


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

maxValue = 0

for i in range(min(N,K)+1):
    for j in range(min(N,K)-i+1):
        left = D[:i]
        right = D[N-j:]
        merge = (left + right + [0])
        merge.sort()

        index = 0

        for k in range(K-i-j):
            if (merge[index] < 0):
                index += 1
            else:
                break

        val = sum(merge[index:])
        if(maxValue < val):
            maxValue = val

print(maxValue)

Measured memory_bytes: 3064
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<string>
#include<map>
#include<set>
#include<math.h>
//#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define ull unsigned long long
#define INF 1e9
#define eps 1e-6
#define PI acos(-1.0)
#define M 10010
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef pair<int, int>P;
const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;

int a[3];

int main() {
	IOS;
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt","w",stdout);
	//a = 999999866000004473;
	//b = 999999822000007597;
    cin >> a[0] >> a[1] >> a[2];
    sort(a,a+3);
    cout << a[2]*10+a[1]+a[0] << endl;
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main()
{
	int a,b,c,d;
	scanf("%d %d %d",&a,&b,&c);
	if(a>b){/*????????則???a???b????????則??????????????\????????????*/
		d=b;b=a;a=d;
	}
	if(b>c){
		d=c;c=b;b=d;
	}
	if(a>b){
		d=b;b=a;a=d;
	}
	printf("%d %d %d\n",a,b,c);
	return 0;
}

Measured memory_bytes: 596
def main():
    n = int(input())
    x = list(map(int, input().split()))

    sort_list = x[:]
    sort_list.sort()

    for i in range(0, n):
        if x[i] < sort_list[n//2]:
            print(sort_list[n//2])
        else:
            print(sort_list[n//2 - 1])

if __name__ == '__main__':
    main()


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

// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;

using namespace std;

#define St first
#define Nd second
#define Pb push_back
#define Mp make_pair
// #define endl "\n"

#define REP(i,a,b) for(int i = a; i <= b; i++)
#define REV(i,a,b) for(int i = a; i >= b; i--)

#define AritSum(a,d,n) ((n)*(2*(a)+((n)-1)*(d)))/2
#define Log(base, num) log2(num)/log2(base)

typedef long long int ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<ll> vl;
typedef pair<ll, ll> pll;

// ************* MAIN *******************

int N, M;


void solve() {
    cin >> N>> M;
    vector<vi> al(N);
    REP(i,0,M-1){
        int a,b;cin>>a>>b;
        al[a-1].push_back(b-1);
        al[b-1].push_back(a-1);
    }

    vi parent(N);
    vector<bool> vis(N);
    queue<int> q;
    q.push(0);
    vis[0]=true;
    while(!q.empty()) {
        int cur = q.front(); q.pop();
        for(int u : al[cur]) {
            if(vis[u]) continue;
            parent[u]=cur;
            vis[u]=true;
            q.push(u);
        }
    }

    for(bool b : vis) if(!b) {
        cout << "No" << endl;
        return;
    }

    cout << "Yes" << endl;
    REP(i,1,N-1) cout << ((i>1)? "\n" :"") << parent[i]+1;
}
/*

g++ -std=c++14 -Wall -Wextra -O2 Test.cpp -o Test

*/
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T=1;
    // cin>>T;
    for (int t = 1; t <= T; t++) {
        // cout << "Case #" << t << ": ";
        solve();
    }
    return 0;
}

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

int main() {
  int A;
  cin >> A;
  int B;
  cin >> B;
  
  if (A==1 && B==2) {
    cout << 3;
  }
  if (A==1 && B==3) {
    cout <<2;
  }
  if (A==2 && B==3) {
    cout <<1;
  }
  if (A==3 && B==1) {
    cout <<2;
  }
  if (A==2 && B==1) {
    cout << 3;
  }
  if (A==3 && B==2) {
    cout <<1;
  }
	return 0;
}

Measured memory_bytes: 3568
while(True):
    n,x=map(int,input().split())
    
    if n == 0 and x==0:
        break
    
    count = 0
    for i in range(1,n+1):
        for j in range(i+1,n+1):
            for k in range(j+1,n+1):
                if i+j+k == x:
                    count += 1
    
    print(count)
    


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

public class Main {
    public static void main(String[] args){
        int n = 0;
        long m = 0L;
        try{
            BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
            String str = reader.readLine();
            String[] s = str.split(" ");
            n = Integer.parseInt(s[0]);
            m = Long.parseLong(s[1]);
        } catch (IOException e){
            e.printStackTrace();
        }
        calc(n,m);
    }

    public static int calc(int n,long m){
        int x,y;
        boolean flg=true;
        m = m / 1000;
        if(m > 20000){
            System.out.println("-1 -1 -1");
            return 0;
        } else{
            int z1 = (int)m % 5;
            n -= z1;
            m = m - z1;
            for (x = 0;x <= n;x++){
                for(y = 0;y <= n-x;y++){
                    if((10 * x + 5 * y + (n - x - y)) == m){
                        System.out.println(x + " " + y + " " + (n-x-y+z1));
                        flg = false;
                        return 0;
                    }
                }
            }
            if(flg){
            System.out.println("-1 -1 -1");
            }
            return 0;
        }
    }
}

Measured memory_bytes: 21844
#include <iostream>
#include <vector>
#include <deque>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <climits>

constexpr int SINT_MAX = std::numeric_limits<int>::max();
constexpr int SINT_MIN = std::numeric_limits<int>::min();

using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;

///////////////////////////////////////////////////

int main()
{
    int N, M;
    string S;
    cin >> N >> M >> S;
    
    vi grid(N+1);
    for (int i = 0; i <= N; ++i)
    {
        grid[i] = (S[i] == '0') ? 0 : -1;
    }
    
    int i = 0;
    deque<int> list;
    while (i < N)
    {
        bool canpass = false;
        for (int m = M; m >= 1 && !canpass; --m)
        {
            if (i + m <= N && grid[N - i - m] == 0)
            {
                i += m;
                list.push_front(m);
                canpass = true;
            }
        }
        if (!canpass)
        {
            cout<< -1 << endl;
            return 0;
        }
    }
    
    for (int d : list)
    {
        cout << d << " ";
    }
    cout << endl;

    /*
    vi dp(N+1, N);
    dp[N] = 0;
    for (int i = N; i >= 0; --i)
    {
        for (int m = 1; m <= M; ++m)
        {
            if (i >= m && grid[i-m] != -1 && dp[i-m] >= dp[i] + 1)
            {
                dp[i-m] = dp[i] + 1;
                grid[i-m] = i;
            }
        }
    }

    if (grid[0] == 0)
    {
        cout << "-1" << endl;
    }
    else
    {
        for(int i = 0; i < N; i = grid[i])
        {
            cout << (grid[i] - i) << " ";
        }
        cout << endl;
    }
    */
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
#ifdef _DEBUG
#define _GLIBCXX_DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
// typedef __int128_t Int;
#define DBG 1
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define loop(n) rep(loop, (0), (n))
#define all(c) begin(c), end(c)
const int INF =
    sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
using pii = pair<int, int>;
template <class T> bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T> bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(12);

  int N;
  cin >> N;
  vector<int> a(N), b(N);
  bool f = true;
  rep(i, 0, N) {
    cin >> a[i] >> b[i];
    f &= a[i] == b[i];
  }
  if (f) {
    cout << 0 << endl;
    return 0;
  }
  int m = INF;
  int sum = 0;
  rep(i, 0, N) {
    if (a[i] > b[i]) {
      chmin(m, b[i]);
    }
    sum += a[i];
  }
  cout << sum - m << endl;

  return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define fix(f,n) std::fixed<<std::setprecision(n)<<f
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long int ll;
typedef unsigned long long int ull;
#define vi vector<int>
#define pii pair<int,int>
#define vii vector<pii>
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a>b)?b:a)
#define max3(a,b,c) ((a>b)?(a>c)?a:c:(b>c)?b:c)
#define min3(a,b,c) ((a<b)?(a<c)?a:c:(b<c)?b:c)
#define REP(i,a,n) for(ll i=a;i<n;i++)
#define pb push_back
#define mp make_pair

int main(){
	fast;
	int test=1;
	while(test--){
	    ll n;
	    cin >> n;
	    ll arr[n+1];
	    for(int i=1 ; i<=n ; i++){
	        cin >> arr[i];
	    }
	    ll dp[n+1];
	    dp[1]=0;
	    dp[2]=abs(arr[2]-arr[1]);
	    for(int i=3 ; i<=n ; i++){
	        dp[i]=min(dp[i-2]+abs(arr[i]-arr[i-2]),dp[i-1]+abs(arr[i]-arr[i-1]));
	    }
	    cout << dp[n] << endl;
	}
	return 0;
}

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

int h, w, n;
int res = 0;
int main(){
  cin >> h >> w >> n;
  if(h > w){ //hがデカイ
    res = n/h;
    res += min(1, n%h);
  }else{
    res = n/w;
    res += min(1, n%w);
  }
  cout << res << endl;
  return 0;
}

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

using namespace std;

typedef long long ll;
typedef pair<int,int> P;
const double EPS = 1e-12;
const int INF = numeric_limits<int>::max()/2;
const int MOD = 1e9+7;
const double EX=1.0/6.0;

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

    int n,t,l,b;
    while(cin>>n>>t>>l>>b){
        if(n==0) return 0;
        vector<vector<double>> dp(t+2,vector<double>(n+1,0));
        dp[0][0]=1;
        vector<int> lose(n+1,0),back(n+1,0);
        for(int i=0;i<l;i++){
            int idx;cin>>idx;
            lose[idx]=1;
        }
        for(int i=0;i<b;i++){
            int idx;cin>>idx;
            back[idx]=1;
        }
        for(int i=1;i<=6;i++){
            int dst=i;
            if(i>n){
                int dif=i-n;
                dst=n-dif;
            }
            dp[1][dst]+=EX;
        }
        for(int i=1;i<t;i++){
            for(int j=1;j<n;j++){
                if(back[j]){
                    dp[i][0]+=dp[i][j];
                    dp[i][j]=0;
                }
            }
            for(int j=0;j<n;j++){
                for(int k=1;k<=6;k++){
                    int dst=j+k;
                    if(dst>n){
                        int dif=dst-n;
                        dst=n-dif;
                    }
                    if(back[j]) continue;
                    else if(lose[j]) dp[i+2][dst]+=dp[i][j]*EX;
                    else dp[i+1][dst]+=dp[i][j]*EX;
                }
            }
        }
        double res=0;
        for(int i=1;i<=t;i++) res+=dp[i][n];
        cout<<fixed<<setprecision(10)<<res<<endl;
    }
}


Measured memory_bytes: 3324
//OPTIMIZATONS
#pragma GCC optimize("02")
//CODE
#include<bits/stdc++.h>
// uncomment the below code to use int as long long
#define int long long
// uncomment the below code to use float as double
//#define float double
#define endl "\n"
#define debug cout<<"Good uptill here"<<endl<<flush;
#define deb(x) cout<<#x<<":"<<x<<endl<<flush;

using namespace std;

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	//CODE FOR SPECIFIED INPUT AND OUTPUT
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n;
	cin>>n;
	int ans = 0;
	for(int i=1;i<=n;i++){
		if(i%3!=0 && i%5!=0) ans += i;
	}
	cout<<ans<<endl;
	return 0;
}



Measured memory_bytes: 3648
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
#define fastAF ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long
#define ull unsigned ll
#define ld long double
#define pb push_back
#define pf push_front
#define dll deque<ll>
#define vll vector<ll>
#define pll pair<ll,ll>
#define mapll map<ll,ll>
#define endl "\n"
#define all(v) v.begin(),v.end()
#define deb(x) cout<<x
#define ms(a,x) memset(a,x,sizeof(a))
using namespace std;
int main()
{
    fastAF
    ll n; cin>>n; ll a[n];
     for(ll i=0;i<n;i++) cin>>a[i];
     sort(a,a+n);
      ll ans=0;
    for(ll i=0;i<n;i++)
    {
    	for(ll j=i+1;j<n;j++) 
    	{
    		for(ll k=j+1;k<n;k++)
    		{
    			if(a[i]==a[j]||a[j]==a[k]||a[k]==a[i]) continue;
    			if(a[i]+a[j]>a[k]) ans++;
    		}
    	}
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3632
package main

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

var sc = bufio.NewScanner(os.Stdin)
const MAX_N = 1e2 + 10

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

func min(x, y int) int {
    if x < y {
        return x
    } else {
        return y
    }
}

func main() {
    sc.Split(bufio.ScanWords)

    n := nextInt()
    var a, b [MAX_N]int

    for i := 0; i < n-1; i++ {
        b[i] = nextInt()
    }
    sum := 0
    a[0] = b[0]
    for i := 1; i < n-1; i++ {
        a[i] = min(b[i], b[i-1])
    }
    a[n-1] = b[n-2]

    for i := 0; i < n; i++ {
        sum += a[i]
    }
    
    fmt.Println(sum)

}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
//#define ll long long
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 (a>b) { a=b; return 1; } return 0; }
#define rep(i, n) REP(i, 0, n)
#define rep_rev(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define all(x) (x).begin(),(x).end()
ll t1,t2,t3;
const ll mod = 1000000007;
const int INF = 1e9;
const ll INFLONG = 1e18;




int main(){
  ll n;
  cin >> n;
  vector<ll> vec(n);
  rep(i,n){
    cin >> vec[i];
  }
  ll ans = -INFLONG;
  vector<vector<vector<ll>>> dp(n+1,vector<vector<ll>>(2,vector<ll>(3,-INFLONG)));
  dp[0][1][1] = 0;
  rep(i,n){
    if(i % 2 == 0){
      rep(j,3){
        chmax(dp[i+1][1][j],dp[i][1][j]);
        chmax(dp[i+1][0][j],dp[i][0][j]);
      }
      chmax(dp[i+1][1][0],dp[i][0][0]);

      chmax(dp[i+1][0][1],dp[i][1][0] + vec[i]);
      chmax(dp[i+1][1][1],dp[i][0][1]);

      chmax(dp[i+1][0][2],dp[i][1][1] + vec[i]);
      chmax(dp[i+1][1][2],dp[i][0][2]);
    }else{
      rep(j,2){
        chmax(dp[i+1][1][j],dp[i][1][j+1]);
        chmax(dp[i+1][0][j],dp[i][0][j+1]);
      }
      chmax(dp[i+1][0][0],dp[i][1][0] + vec[i]);
      chmax(dp[i+1][1][0],dp[i][0][1]);

      chmax(dp[i+1][0][1],dp[i][1][1] + vec[i]);
      chmax(dp[i+1][1][1],dp[i][0][2]);
    }
  }
//    rep(i,n+1){
//      rep(j,2){
//        rep(k,3){
//          cout << dp[i][j][k];
//        }
//        cout << " ";
//      }
//      cout << endl;
//    }
  ans = max(dp[n][0][1],dp[n][1][1]);
  cout << ans << endl;
}

Measured memory_bytes: 34412
#include <bits/stdc++.h>
using namespace std;
typedef bool boolean;

const int N = 1e5 + 5;

#define ll long long
#define par pair<ll, int>

int n;
par a[N];
int Fa[N];
int sz[N], uf[N], d[N];
vector<pair<int, int>> E;

int find(int x) {
	return uf[x] == x ? x : (uf[x] = find(uf[x]));
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i].first);
		a[i].second = i;
		sz[i] = 1;
		uf[i] = i;
	}
	sort(a + 1, a + n + 1);
	for (int i = n; i > 1; i--) {
		ll d = a[i].first;
		int p = a[i].second;
		int fa = lower_bound(a + 1, a + n + 1, par(d - n + (sz[p] << 1), 0)) - a;
		if (a[fa].first != d - n + (sz[p] << 1)) {
			puts("-1");
			return 0;
		}
		if (find(p) == find(fa = a[fa].second)) {
			puts("-1");
			return 0;
		}
		sz[fa] += sz[p];
		E.emplace_back(p, fa);
		Fa[p] = fa;
	}
	ll f1 = 0;
	for (int i = 2; i <= n; i++)
		f1 += (d[a[i].second] = d[Fa[a[i].second]] + 1);
	if (f1 ^ a[1].first) {
		puts("-1");
		return 0;
	}
	for (auto x : E)
		printf("%d %d\n", x.first, x.second);
	return 0;
}


Measured memory_bytes: 5364
#include <iostream>
#include <string>
#include <vector>

int main(){

	std::string s;
	std::cin >>s;
	if(s[3]==s[2] and s[4]==s[5]){
		std::cout <<"Yes" <<std::endl;
	}else{
		std::cout <<"No" <<std::endl;
	}
	return 0;
}


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

using namespace std;

int main(void) {
	int i, j;
	string s, t;
	cin >> s >> t;
	for (i = s.size() - t.size(); i >= 0; i--) {
		for (j = 0; j < t.size(); j++) {
			if (s[i + j] != '?' && s[i + j] != t[j])
				break;
		}
		if (j == t.size())
			break;
	}
	if (i < 0)
		printf("UNRESTORABLE\n");
	else {
		for (j = 0; j < t.size(); j++)
			s[i + j] = t[j];
		for (i = 0; i < s.size(); i++) {
			if (s[i] == '?')
				s[i] = 'a';
		}
		cout << s << "\n";
	}
	return 0;
}

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

int main() {
	int n;
	cin >> n;
	vector<int> l(n);
	for (int i = 0; i < n; i++)
		cin >> l[i];
	sort(l.begin(), l.end());
	int sum = 0;
	for (int i = 0; i < n - 1; i++)
		sum += l[i];
	if (sum > l[n - 1])
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	return 0;
}

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

vector<vector<int>> memo(100, vector<int>(100, -1));
int f(const vector<vector<char>> &s ,int i, int j){
  if(i == 0 && j == 0) {
    memo[i][j] = 0;
    return 0;
  }
  int ans1=300, ans2=300;
  if(i - 1 >= 0){
    if(s[i][j] == s[i - 1][j]){
      ans1 = (memo[i - 1][j] == -1)?f(s, i - 1, j):memo[i - 1][j];
    }else{
      ans1 = (memo[i - 1][j] == -1)?f(s, i - 1, j) + 1:memo[i - 1][j] + 1;
    }
  }
  if(j - 1 >= 0){
    if(s[i][j] == s[i][j - 1]){
      ans2 = (memo[i][j - 1] == -1)?f(s, i, j - 1):memo[i][j - 1];
    }else{
      ans2 = (memo[i][j - 1] == -1)?f(s, i, j - 1) + 1:memo[i][j - 1] + 1;
    }
  }
  memo[i][j] = min(ans1, ans2);
  return min(ans1, ans2);
}

int main() {
  int h, w;
  cin >> h >> w;
  vector<vector<char>> s(h,vector<char>(w));
  rep(i,h) rep(j,w) cin >> s[i][j];
  h--, w--;
  
  if(s[0][0] == '#') cout << (f(s, h, w) + 2)/2 << endl;
  else cout << (f(s, h, w) + 1)/2 << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define F(i,a,b) for(ll i=a;i<=b;i++)
#define FB(i,a,b) for(ll i=a;i>=b;i--)
#define PB(x) push_back(x)
#define MP(x,y) make_pair(x,y)
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define SC second
#define FS first
using namespace std;
const int N=1e5+5;

char A[N],B[N];

 int main()
 {
	ll n,m;
	scanf("%lld%lld",&n,&m);
	scanf("%s",(A+1));
	scanf("%s",(B+1));

	if(n==1&&m==1)
	{
		if(A[1]!=B[1])
		{
			printf("-1\n");
			return 0;
		}

		printf("1\n");
		return 0;
	}

	ll NW=n*m/__gcd(n,m);

	ll I=1;
	ll J=1;
	int i=1;
	int j=1;

	bool res = true;

	while(i<n||j<m)
	{
		if(I==J) res=res&&(A[i]==B[j]), i++, I+=(NW/n);
	       	else if(I<J) i++, I+=(NW/n);
		else j++, J+=(NW/m);	
	}

	if(!res) printf("-1\n");
	else printf("%lld\n",NW);
 }



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

uint32_t combination( uint32_t n ){
  if( n <= 1 ){
    return 0;
  }

  uint32_t a = 1;
  for( uint32_t i = n; i > n-2; --i ){
    a *= i;
  }

  return a / 2;
}

int main(){
  uint32_t N, M;
  cin >> N >> M;

  uint32_t n = combination( N );
  uint32_t m = combination( M );

  cout << n + m << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int x[n];
    for(int i=0;i<n;i++){
        cin>>x[i];
    }
    for(int i=n-1;i>0;i--){
        cout<<x[i]<<' ';
        
    }
    cout<<x[0]<<endl;
}


Measured memory_bytes: 3080
#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
/************************************************/
#define rep(i,n) for(int i=0;i<n;i++)
#define m_p make_pair
#define pb push_back
#define fr first
#define se second
#define forn(i,a,n) for(int i=a;i<n;i++)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define sz(s) s.size()
#define all(s) s.begin(),s.end()
#define zero(x) memset(x,0,sizeof(x))
#define vii vector<pair<int,int> >
#define mpis map<int,string>
#define mpii map<int,int>
#define mpsi map<string,int>
#define re return
#define mod 1000000007
/************************************************/
using namespace std;

long long get(){
	char c=getchar();
	long long x=0LL;
	while(c<'0'||c>'9')
	c=getchar();
	while(c>='0'&&c<='9'){
		x*=10LL;
		x+=(c-'0');
		c=getchar();
	}
	return x;
}
int n,m;
int h[100001];
int a[100001],b[100001];
bool f[100001];
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>m;
	rep(i,n)
	cin>>h[i];
	rep(i,m){
		cin>>a[i]>>b[i];
		a[i]--;
		b[i]--;
		if(h[a[i]]>=h[b[i]])
		f[b[i]]=true;
		if(h[b[i]]>=h[a[i]])
		f[a[i]]=true;
	}
	int ans=0;
	rep(i,n)
	if(!f[i]){
		ans++;
	}
	
	cout<<ans;
	re 0;
}

Measured memory_bytes: 4924
n = int(input())
h = list(map(int, input().split()))
highest = h[0]
for i in range(n-1):
    if h[i+1] - h[i] < -1:
        print("No")
        exit()
    if h[i+1] - h[i] == -1:
        if highest > h[i+1] + 1:
            print("No")
            exit()
        else:
            highest = h[i]
print("Yes")

Measured memory_bytes: 14396
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int ans = 0;
		char[] S = sc.next().toCharArray();
		char[] T = sc.next().toCharArray();
		for(int i = 0; i < 3; i++)
			if(S[i] == T[i])
				ans++;
		System.out.println(ans);

	}

}

Measured memory_bytes: 21844
def main():
    N, M = map(int, input().split())
    S = [list(map(lambda x: int(x) - 1, input().split()))[1:] for _ in range(M)]
    P = list(map(int, input().split()))

    ans = 0
    for bit in range(1 << N):
        for i in range(M):
            on = 0
            for j in S[i]:
                if bit & (1 << j):
                    on += 1
            if on % 2 != P[i]:
                break
        else:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()


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

int main() {
    int N;
    cin >> N;
    
    long int sum = 0;
    for (int i = 1; i <= N; i++) {
        if (i % 5 != 0 && i % 3 != 0)
            sum += i;
    }
    
    cout << sum << endl;
    
    return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define ri rd<int>
#define rep(i, a, b) for (int i = (a), _ = (b); i <= _; ++i)
#define per(i, a, b) for (int i = (a), _ = (b); i >= _; --i)
#define For(i, a, b) for (int i = (a), _ = (b); i < _; ++i)
typedef long long LL;

template<class T> T rd() {
	bool f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = 0;
	T x = 0; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; return f ? x : -x;
}

int n;
LL s, res = 0;
map<LL, int> mp;

int main() {

	n = ri();
	++mp[s = 0];
	rep (i, 1, n) {
		s += ri();
		res += mp[s]++;
	}
	printf("%lld\n", res);

	return 0;
}


Measured memory_bytes: 12800
#include<stdio.h>
int main(){
int H,W,h,w;
while(1){
scanf("%d%d",&H,&W);
if(H==0&&W==0)break;
for(h=1;h<=H;h++){
  for(w=1;w<=W;w++){
    if(h%2==1){
      if(w%2==1)putchar('#');
      else putchar('.');}
    else{
      if(w%2==1)putchar('.');
      else putchar('#');}
}
  putchar('\n');}
putchar('\n');}
return 0;
}



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

using namespace std;
typedef pair<int, int>P;
typedef long long ll;
#define rep(i,n)for(ll i=0;i<n;++i)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const double pi = acos(-1.0);
const ll MOD = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 5010;
//max=({});
//条件式が真ならwhileの中身を回し続ける
//printf("%d\n", ans);

//pairの入力
//vector<pair<ll, ll>>work(n);
//rep(i, n) {
//	ll a, b;
//	cin >> a >> b;
//	work[i] = make_pair(a, b);
//for(auto p:mp)(mapの探索)
//printf("%.10f\n",なんちゃら)
//最大公約数
ll gcd(ll x, ll y) {
	return y ? gcd(y, x % y) : x;
}

ll lcm(ll x, ll y) {
	if (x == 0 || y == 0)return 0;
	return (x / gcd(x, y) * y);
}

//組み合わせの余りを求める
ll fac[MAX_N], finv[MAX_N], inv[MAX_N];
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX_N; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(ll n, ll k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll dx[4] = { 0,0,-1,1 };
ll dy[4] = { -1,1,0,0 };
ll dp[101010];

//union-find木について
ll par[101010];
ll rank2[101010];

void init(ll n) {
	rep(i, n) {
		par[i] = i;
		rank2[i] = 0;
	}
}

ll find(ll x) {
	if (par[x] == x) {
		return x;
	}
	else {
		return par[x] = find(par[x]);
	}
}

void unite(ll x, ll y) {
	x = find(x);
	y = find(y);
	if (x == y)return;
	if (rank2[x] < rank2[y]) {
		par[x] = y;
	}
	else {
		par[y] = x;
		if (rank2[x] == rank2[y]) {
			rank2[x]++;
		}
	}
}

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

//long longしか使わない
//素数は1より大きい
int main() {
	string s;
	cin >> s;
	string ans = s.substr(0, 3);
	cout << ans << endl;
	return 0;
}


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

using namespace std;

int main(int argc, char const* argv[])
{
	int n;
	cin >> n;
	string str;
	cin >> str;
	int min;
	int prev;
	int count = 0;
	for(int i = 1; i < str.size(); i++){
			if(str[i] == 'E')count++;
	}
	min = count;
	prev = count;
	for(int i = 1; i < str.size(); i++){
			if(str[i-1] == 'W')prev++;
			if(str[i] == 'E')prev--;
			if(prev < min) min = prev;
	}
	cout << min << endl;
	return 0;
}



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

int main() {
  int N, i, j;
  int cnt = 0;
  cin >> N;
  vector<int> button(N);
  for (i = 0; i < N; i++) {
    cin >> button.at(i);
  }
  j = button.at(0) - 1;
  for (i = 0; i < N; i++) {
    cnt++;
    if (cnt > (N - 1)) {
      cout << "-1" << endl;
      break;
    }
    if (j == 1) {
      cout << cnt << endl;
      break;
    } else {
      j = button.at(j) - 1;
    }
  }
  
}

Measured memory_bytes: 640
N = int(input())
MODN = int(1e9 + 7)

D = {}
X = [0] * N

for i in range(N):
  c = int(input())
  if not c in D:
    X[i] = 1 if i == 0 else X[i-1]
    D[c] = i
    continue
    
  X[i] = (X[i-1] + X[D[c]]) % MODN if D[c] < i-1 else X[i-1]
  D[c] = i
    
print(X[N-1])

Measured memory_bytes: 34184
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

void main()
{
    auto X = readln.chomp.to!int;
    int r = 1;
    foreach (i; 1..X+1) {
        foreach (j; 2..X+1) {
            if (i^^j <= X) r = max(r, i^^j);
        }
    }
    writeln(r);
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * Created by wild on 16/08/13.
 */
public class Main {
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        char[] s = scan.next().toCharArray();
        List<String> result = new ArrayList<>();

        for (int i = 0; i < s.length; i++){
            switch (s[i]){
                case '0':
                    result.add("0");
                    break;
                case '1':
                    result.add("1");
                    break;
                case 'B':
                    if (result.size() != 0){
                        result.remove(result.size()-1);
                    }
                    break;
            }
        }

        for (int i = 0; i < result.size(); i++){
            System.out.print(result.get(i));
        }
    }
}

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

int main() {
	int n, x, d = 1;
	int xi[(int)1e5];
	int yi[(int)1e5];

	cin >> n >> x;

	int min = 1e9;

	for (int i = 0; i < n; i++) {
		cin >> xi[i];
		yi[i] = abs(xi[i] - x);
		min = (min < yi[i]) ? min : yi[i];
	}

	bool divisible;

	for (int i = min; i >= 1; i--) {
		divisible = true;
		for (int j = 0; j < n; j++) {
			if (yi[j] % i != 0) {
				divisible = false;
				break;
			}
		}
		if (divisible) {
			d = i;
			break;
		}
	}

	cout << d << endl;

	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define nl "\n"
#define rep(i,n) for(ll i=0; i<(n); i++)
#define INF ((1LL<<62)-(1LL<<31))
#define MOD 1000000007 //998244353
typedef vector<ll> vl;
typedef vector<vl> matrix;//A(n, vl(m)); //n*m行列
typedef vector<string> vs;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
typedef vector<bool> vb;
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define Sortup(V) sort(V.begin(), V.end())
#define Sortdown(V) sort(V.rbegin(), V.rend())
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;}
void CumuSum(vl &A){rep(i,A.size())if(i)A[i]+=A[i-1];}
ll llpow(ll e,ll x){ll res=1LL;while(x){if(x&1)res*=e;e*=e;x/=2;}return res;}
ll llpowMOD(ll e,ll x){ll res=1LL;while(x){if(x&1)res*=e;e*=e;x/=2;res%=MOD;e%=MOD;}return res;}
bool bit(ll subset, ll Rsift){ return ((subset)>>(Rsift))&1; }

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

    // solution comes here

    ll A, B;
    cin >> A >> B;
    vl a(3);
    a[A-1]++;
    a[B-1]++;
    rep(i, 3){
        if(!a[i]){
            cout << i+1 << nl;
            return 0;
        }
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_map>

using namespace std;

typedef long long int int64;

int main(int argc, char **argv)
{
    int N, W;
    cin >> N >> W;

    int64 dp[N + 1][W + 1];
    for (int j = 0; j <= W; ++j) dp[0][j] = 0;

    for (int i = 1; i <= N; ++i) {
        int w, v;
        cin >> w >> v;
        for (int j = 0; j <= W; ++j) {
            if (w <= j) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v);
            else dp[i][j] = dp[i - 1][j];
        }
    }

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


Measured memory_bytes: 79104
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    vint cnt(3,0);
    string abc = "abc";
    REP(i,3){
        REP(j,3){
            if(s[i]==abc[j]){
                cnt[j]++;
            }
        }
    }
    REP(i,3){
        if(cnt[i]==0){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;

    return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;


#define pb push_back
#define ff first
#define ss second
#define INF int(3e9)
#define BIG_INF ll(9e18)
#define SIZE 100001
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define len(v) int((v).size())
#define sqr(x) (x) * (x)
#define cube(x) (x) * (x) * (x)
#define filein freopen("input.txt", "r", stdin)
#define fileout freopen("output.txt", "w", stdout);


ll binpow(ll a, ll b, ll MOD = BIG_INF)
{
    ll res = 1;

    while(b)
    {
        if(b & 1)
            res *= a;
        a *= a;
        b >>= 1;
        a %= MOD;
        res %= MOD;
    }

    return res % MOD;
}

const ll mod = 1e9 + 7;

int T = 1;
ll n, m;
string s;
vector<int> a;

int to[256];



void solve()
{
    cin >> n;

    ll ans = 0;
    for(int i = 1; i <= n; i++)
    {
        ans += i;
        if(i % 3 == 0 || i % 5 == 0) ans -= i;
    }
    cout << ans;
    return;
}


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

//    cin >> T;

    while(T--)
    {
        solve();
    }
    return 0;
}


Measured memory_bytes: 3584
#include <iostream>
#include <cstring>
#include <vector>
#include <set>
#include <list>
#include <map>
#include <deque>
#include <algorithm>
#include <utility>
#include <stdio.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
#define for1(i,n) for (ll i=0;i<(n);i++)
#define for2(i,m,n) for (ll i=(m);i<(n);i++)
#define for3(i,m,n,d) for (ll i=(m);i<(n);i+=(d))
#define DEBUG 0

ll N;
ll A[100010];

void solve()
{
    vector<string> anss;
    char cs[1000] = {0};
    cin >> N;
    for1(i,N) {
        cin >> A[i];
    }
    sort(&A[0],&A[N]);

    for2(i,1,N-1) {
        if (A[i] > 0) {
            sprintf(cs, "%lld %lld", A[0], A[i]);
            anss.push_back(string(cs));
            A[0] -= A[i];
        }
    }

    sprintf(cs, "%lld %lld", A[N-1], A[0]);
    anss.push_back(string(cs));
    ll ans = A[N-1] - A[0];

    for2(i,1,N-1) {
        if (A[i] <= 0) {
            sprintf(cs, "%lld %lld", ans, A[i]);
            anss.push_back(string(cs));
            ans -= A[i];
        }
    }

    cout << ans << endl;
    for (string s : anss) {
        cout << s << endl;
    }
}

int main()
{
    do {
        solve();
    } while (DEBUG);
}


Measured memory_bytes: 9588
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  ll n;
  cin >> n;
  map<char, ll> mp;
  rep(i, n) {
    string s;
    cin >> s;
    mp[s[0]]++;
  }
  vc c = {'M', 'A', 'R', 'C', 'H'};
  ll ans = 0;
  rep(i, 3) rep2(j, i + 1, 4) rep2(k, j + 1, 5) {
    ans += mp[c[i]] * mp[c[j]] * mp[c[k]];
  }
  cout << ans << endl;
}

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

int main()
{
    int h,w,t,maxh=0,maxw=0;
    long taikakusen[200][200],max=0;
    
    //??¢?´¢ i=w j=h
    for(int i=1;i<=150;i++){
        for(int j=1;j<i;j++){
            taikakusen[i][j] = i*i + j*j;
        }
    }
    
    cin>>h>>w;
    
    while(h != 0 && w != 0){
        t = h*h + w*w;
        for(int i=1;i<=150;i++){
            for(int j=1;j<i;j++){
                if(t<taikakusen[i][j]){
                    if(max==0){
                        maxh=j;
                        maxw=i;
                        max=taikakusen[i][j];
                    }
                    else if(taikakusen[i][j]==max){
                        if(j<maxh){
                            maxh=j;
                            maxw=i;
                        }
                    }
                    else if(taikakusen[i][j]<max){
                        maxh=j;
                        maxw=i;
                        max=taikakusen[i][j];
                    }
                }
                if(t==taikakusen[i][j] && j>h){
                    maxh=j;
                    maxw=i;
                    max=taikakusen[i][j];
                }
            }
        }
        
        cout<<maxh<<" "<<maxw<<"\n";
        maxh=0;
        maxw=0;
        max=0;
        
        cin>>h>>w;
    }
    
    return 0;
}

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

int main () {
    int N;
    cin >> N;
    vector<int> mochi(N);
    for (int i = 0; i < N; i++) {
        cin >> mochi.at(i);
    }
    sort(mochi.begin(), mochi.end());
    reverse(mochi.begin(), mochi.end());

    int sum = 1;
    for (int i = 0; i < mochi.size(); i++) {
        if (i != 0 && mochi.at(i) != mochi.at(i - 1)) {
            sum++;
        }
    }
    cout << sum << endl;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Main {

	public static final MyScanner in = new MyScanner();

	public static void main(String[] args) {

        int N = in.nextInt();
        int K = in.nextInt();
        int R = in.nextInt();
        int S = in.nextInt();
        int P = in.nextInt();
        char[] T = in.next().toCharArray();

        char r = 'r';
        char s = 's';
        char p = 'p';
        char w = 'w';

        int score = 0;
        for(int i=0; i < N; i++) {
        	if(i >= K) {
        		if (T[i-K] == T[i]) {
        			T[i] = w;
        			continue;
        		}
        	}
        	if (T[i] == r) {
        		score+=P;
        	} else if(T[i] == s) {
        		score+=R;
        	} else if(T[i] == p) {
        		score+=S;
        	}
        }
        System.out.println(score);

	}

	public static class MyScanner{
		Scanner sc = new Scanner(System.in);
		String nextLine() {return sc.nextLine();}
		String next() {return sc.next();}
		int nextInt() {return Integer.valueOf(sc.next());}
		long nextLong() { return Long.valueOf(sc.next());}
	}
}

Measured memory_bytes: 27860
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <numeric>
#include <ctime>
#include <complex>
#include <bitset>
#include <random>
#include <stack>

//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimmize("unroll-loops")

using namespace std;

typedef long long ll;
typedef long double ld;

#define int ll
#define double ld
#define loop(i, n) for(int i = 0; i < (int)n; ++i)
#define loop1(i, n) for(int i = 1; i <= (int)n; ++i)
#define F first
#define S second
#define pb push_back
#define pi pair <int, int>
#define all(x) begin(x), end(x)
#define ti tuple <int, int, int>
#define Point Vect
#define mkt make_tuple
#define no {cout << "-1\n"; return;}

const int MOD = 1e9 + 7, rev2 = 500000004;

void solve() {
    int n; cin >> n;
    vector <int> a(n);
    int sum = 0;
    loop(i, n) {
        cin >> a[i];
        sum = (sum + a[i]) % MOD;
    }
    sum = sum * sum % MOD;
    loop(i, n)
        sum = (sum - a[i] * a[i] % MOD + MOD) % MOD;
    cout << sum * rev2 % MOD;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //int t; cin >> t; loop(i, t)
    solve();
    return 0;
}

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

using namespace std;

int main() {
    int n; cin >> n;
    vector <int> v (n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    int cur = 1;
    for (int i = 0; i < n; i++) {
        if (v[i] == cur) {
            cur++;
        }
    }
    if (cur == 1) {
        cout << -1 << "\n";
    } else {
        cout << n - cur + 1 << "\n";
    }
}

Measured memory_bytes: 3940
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...)name
#define _rep(i,n)repi(i,0,n)
#define repi(i,a,b)for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x)x
#define rep(...)MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c)c.begin(),c.end()
#define write(x)cout<<(x)<<'\n'
using namespace std; typedef long long ll; template<class T>using vv = vector<vector<T>>;
template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
template<class T, class U>bool chmax(T& a, U&& b) { return a < b ? a = b, 1 : 0; }
template<class T, class U>bool chmin(T& a, U&& b) { return b < a ? a = b, 1 : 0; }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

ll mpow(ll x, ll n) { ll y = 1; for (; n > 0; n /= 2) { y = n % 2 ? y * x % MOD : y; x = x * x % MOD; } return y; }
struct Combination {
    vector<ll> fact, ifact;
    Combination(int n) : fact(n + 1), ifact(n + 1) {
        fact[0] = 1; for (int i = 0; i < n; ++i) fact[i + 1] = fact[i] * (i + 1) % MOD;
        ifact[n] = mpow(fact[n], MOD - 2); for (int i = n; i > 0; --i) ifact[i - 1] = ifact[i] * i % MOD;
    }
    ll operator ()(int n, int k) { return k < 0 || k > n ? 0 : fact[n] * ifact[n - k] % MOD * ifact[k] % MOD; }
} C(1e5);

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

    vector<ll> Xsum(N), ta(N - 1), tb(N - 1);
    rep(i, 1, N - 1) ta[i] = (ta[i - 1] + (X[i] - X[0])) % MOD;
    rep(i, 1, N - 1) tb[i] = (tb[i - 1] + (X[N - 2] - X[N - 2 - i])) % MOD;

    ll ans = 0;
    rep(i, N - 1) {
        //rep(j, i + 1, N - 1) {
        //    //ans = (ans + (X[j] - X[i]) * C(N - 1, j - i - 1) % MOD * C.fact[j - i - 1] % MOD * C.fact[N - 1 - (j - i + 1)]) % MOD;
        //    //ans = (ans + (X[j] - X[i]) * mpow(N - 1 - (j - i), MOD - 2) % MOD * mpow(N - 1 - (j - i - 1), MOD - 2)) % MOD;
        //    ans = (ans + (X[j] - X[i]) * mpow(N + i - j - 1, MOD - 2) % MOD * mpow(N + i - j, MOD - 2)) % MOD;
        //}
        //ans = (ans + (X[N - 1] - X[i]) * C(N - 1, N - 1 - i) % MOD * C.fact[N - 1 - i - 1] % MOD * C.fact[i]) % MOD;
        ans = (ans + (X[N - 1] - X[i]) * mpow(N - 1 - i, MOD - 2)) % MOD;
    }
    rep(k, 1, N - 1) {
        ans = (ans + (k * (X[N - 2] - X[0]) - (ta[k - 1] + tb[k - 1])) % MOD * mpow(N - 1 - k, MOD - 2) % MOD * mpow(N - k, MOD - 2) % MOD + MOD) % MOD;
    }
    write(ans * C.fact[N - 1] % MOD);
}

Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=5005,INF=1<<28;
vector<pair<int,ll>> G[MAX];
ll dis[MAX];
int H,W;

void dijkstra(vector<int> s){
    
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> PQ;
    
    for(int j:s){
        dis[(H-1)*W+j]=0;
        dis[H*W+(H-1)*W+j]=0;
        
        PQ.push(make_pair(0,(H-1)*W+j));
        PQ.push(make_pair(0,H*W+(H-1)*W+j));
    }
    
    while(!PQ.empty()){
        ll a=PQ.top().first;
        int b=PQ.top().second;
        PQ.pop();
        if(dis[b]<a) continue;
        for(int i=0;i<G[b].size();i++){
            int c=G[b][i].first;
            ll d=G[b][i].second;
            if(dis[c]>dis[b]+d){
                dis[c]=dis[b]+d;
                PQ.push(make_pair(dis[c],c));
            }
        }
    }
    return;
}//a,dが長さ

vector<int> dh={-2,-1,-1,0,0,0,1,1,2},lw={-1,-2,-1,-3,-2,-1,-2,-1,-1},rw={1,1,2,1,2,3,1,2,1};

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    while(1){
        cin>>W>>H;
        if(H+W==0) break;
        
        for(int i=0;i<2*H*W;i++){
            dis[i]=INF;
            G[i].clear();
        }
        
        vector<vector<char>> S(H,vector<char>(W));
        vector<int> s,g;
        
        for(int i=0;i<H;i++){
            for(int j=0;j<W;j++){
                cin>>S[i][j];
                if(S[i][j]=='S') s.push_back(j);
                if(S[i][j]=='T') g.push_back(j);
            }
        }
        
        for(int i=0;i<H;i++){
            for(int j=0;j<W;j++){
                for(int k=0;k<9;k++){
                    int toh=i+dh[k],tow=j+rw[k];
                    
                    if(toh<0||toh>=H||tow<0||tow>=W) continue;
                    
                    if(S[toh][tow]=='X') continue;
                    
                    if(S[toh][tow]=='S'||S[toh][tow]=='T'){
                        G[i*W+j].push_back({H*W+toh*W+tow,0});
                    }else{
                        G[i*W+j].push_back({H*W+toh*W+tow,int(S[toh][tow]-'0') });
                    }
                }
                
                for(int k=0;k<9;k++){
                    int toh=i+dh[k],tow=j+lw[k];
                    
                    if(toh<0||toh>=H||tow<0||tow>=W) continue;
                    
                    if(S[toh][tow]=='X') continue;
                    
                    if(S[toh][tow]=='S'||S[toh][tow]=='T'){
                        G[H*W+i*W+j].push_back({toh*W+tow,0});
                    }else{
                        G[H*W+i*W+j].push_back({toh*W+tow,int(S[toh][tow]-'0') });
                    }
                }
            }
        }
        
        dijkstra(s);
        
        ll ans=INF;
        
        for(int j:g){
            ans=min(ans,dis[j]);
            ans=min(ans,dis[H*W+j]);
        }
        
        if(ans==INF) cout<<-1<<endl;
        else cout<<ans<<endl;
    }
}





Measured memory_bytes: 4176
#include <bits/stdc++.h>
using namespace std;
int n;
long long a[100005];
int l[100005];
int r[100005];
int main(){
	cin>>n;for(int i=1;i<=n;i++)cin>>a[i];
	a[0]=a[n+1]=-1000000000;
	stack<pair<int,int> >s;
	for(int i=1;i<=n+1;i++){
		while(!s.empty()&&s.top().first>a[i]){
			int h=s.top().first;
			int jb=s.top().second;
			r[jb]=i;
			s.pop();
		}
		s.push({a[i],i});
	}
	while(!s.empty())s.pop();
	for(int i=n;i>=0;i--){
		while(!s.empty()&&s.top().first>a[i]){
			int h=s.top().first;
			int jb=s.top().second;
			l[jb]=i;
			s.pop();
		}
		s.push({a[i],i});
	}
	long long res=0;
	for(int i=1;i<=n;i++)
		res=max(res,a[i]*(r[i]-l[i]-1));
	cout<<res<<"\n";
	return 0;
}



Measured memory_bytes: 4944