1036D - Vasya and Arrays - CodeForces Solution


greedy two pointers *1600

Please click on ads to support us..

Python Code:

import gc
import heapq
import itertools
import math
import sqlite3
from collections import Counter, deque, defaultdict
from sys import stdout
import time
from math import factorial, log, gcd
import sys
from decimal import Decimal
import threading
from heapq import *


def S():
    return sys.stdin.readline().split()


def I():
    return [int(i) for i in sys.stdin.readline().split()]


def II():
    return int(sys.stdin.readline())


def IS():
    return sys.stdin.readline().replace('\n', '')


def main():
    n, a = II(), I()
    m, b = II(), I()
    s1, s2 = map(sum, [a, b])
    if s1 != s2:
        print(-1)
        return
    if a == b:
        print(n)
        return
    idx_a = 1
    idx_b = 0
    s_a = a[0]
    s_b = 0
    ans = 0
    while True:
        if s_a > s_b:
            s_b += b[idx_b]
            idx_b += 1
        elif s_a < s_b:
            s_a += a[idx_a]
            idx_a += 1
        else:
            ans += 1
            if idx_a == n:
                break
            idx_a += 1
            s_a = a[idx_a - 1]
            s_b = 0
    print(ans)


if __name__ == '__main__':
            main()

C++ Code:

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <complex>
#include <queue>
#include <set>
#include <unordered_set>
#include <list>
#include <chrono>
#include <random>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <stack>
#include <iomanip>
#include <fstream>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
typedef pair<double,double> pdd;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<vector<int> > vv32;
typedef vector<vector<ll> > vv64;
typedef vector<vector<p64> > vvp64;
typedef vector<p64> vp64;
typedef vector<p32> vp32;
ll MOD = 998244353;
double eps = 1e-12;
#define forn(i,e) for(ll i = 0; i < e; i++)
#define forsn(i,s,e) for(ll i = s; i < e; i++)
#define rforn(i,s) for(ll i = s; i >= 0; i--)
#define rforsn(i,s,e) for(ll i = s; i >= e; i--)
#define dbg(x) cout<<#x<<" = "<<x<<ln
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define INF 2e18
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())



void solve(){
    ll n1;
    cin>>n1;

    ll a[n1];
	ll sum1=0;
    forn(i,n1){
        cin>>a[i];
		sum1+=a[i];
    }
	
	ll n2;
	cin>>n2;
	ll sum2=0;
    ll b[n2];
	forn(i,n2){
		cin>>b[i];
		sum2+=b[i];
	}
	
	if(sum1!=sum2){
		cout<<-1<<endl;
		return;
	}
	
	ll x=a[0],y=b[0];
	ll i=1,j=1;
	ll ans=0;
	while(i<n1 && j<n2){
		if(x<y){
			x+=a[i];
			i++;
		}
		else if(y<x){
			y+=b[j];
			j++;
		}
		else{
			ans++;
			x=a[i];
			y=b[j];
			i++;
			j++;
		}
	}
	
	ans++;
	
	cout<<ans<<endl;
}


int main()
{
    fast_cin();
    ll t=1;
    // cin >> t;
    for(int ix=1;ix<=t;ix++) {
        solve();
    }
    return 0;
}
   		 			 	 			 	  	 			 	  	 	


Comments

Submit
0 Comments
More Questions

507B - Amr and Pins
379A - New Year Candles
1154A - Restoring Three Numbers
750A - New Year and Hurry
705A - Hulk
492B - Vanya and Lanterns
1374C - Move Brackets
1476A - K-divisible Sum
1333A - Little Artem
432D - Prefixes and Suffixes
486A - Calculating Function
1373B - 01 Game
1187A - Stickers and Toys
313B - Ilya and Queries
579A - Raising Bacteria
723A - The New Year Meeting Friends
302A - Eugeny and Array
1638B - Odd Swap Sort
1370C - Number Game
1206B - Make Product Equal One
131A - cAPS lOCK
1635A - Min Or Sum
474A - Keyboard
1343A - Candies
1343C - Alternating Subsequence
1325A - EhAb AnD gCd
746A - Compote
318A - Even Odds
550B - Preparing Olympiad
939B - Hamster Farm